Efficient noise-tolerant learning from statistical queries

In this paper, we study the problem of learning in the presence of classifi cation noise in the probabilistic learning model of Valiant and its variant s. In order to identify the class of "robust" learning algorithms in the mo st general way, we formalize a new but related model of learning from stati stical queries. Intuitively, in this model, a learning algorithm is forbidd en to examine individual examples of the unknown target function, but is gi ven access to an oracle providing estimates of probabilities over the sampl e space of random examples. One of our main results shows that any class of functions learnable from st atistical queries is in fact learnable with classification noise in Valiant 's model, with a noise rate approaching the information-theoretic barrier o f 1/2. We then demonstrate the generality of the statistical query model, s howing that practically every class learnable in Valiant's model and its va riants can also be learned in the new model (and thus can be learned in the presence of noise). A notable exception to this statement is the class of parity functions, which we prove is not learnable from statistical queries, and for which no noise-tolerant algorithm is known.