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