# Statistical query model algorithms?

I asked this question 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?

• what is the statistical query model ? – Suresh Venkat Nov 14 '10 at 21:39
• from Kearns paper 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 Nov 14 '10 at 21:52

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). 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) or this recent paper by Gupta et al. (Privately Releasing Conjunctions and the Statistical Query Barrier)

• really nice answer Aaron :) many thanks :) – Deyaa Nov 15 '10 at 8:28

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 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.

• Interesting. Do you have a reference that parities can not be learned in SQ model ? – Mohammad Alaggan Nov 17 '10 at 2:40
• it was proven by Kearns in his original paper defining the model: 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 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 Nov 17 '10 at 6:09

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.

• 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 Jun 16 '11 at 17:54