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.