statistical queries model

Main paper: efficient noise-tolerant learning from statistical queries

Statistical query, defined on page 2 of the paper

Theorem (learning with noise): Any class efficiently learnable with statistical queries is also efficiently learnable with an examples oracles (of the kind used in standard PAC learning) with classification noise.

SQ model is less powerful than PAC learning. The fact that practically every concept class known to be eciently learnable in the Valiant model can in fact be learned from statistical queries (and thus with classication noise) raises the natural question of whether the two models are equivalent. We answer this question negatively in Section 7 by proving that the class of parity concepts, known to be eciently learnable in the Valiant model, cannot be eciently learned from statistical queries. The class of parity concepts is also notorious for having no known ecient noise-tolerant algorithm