Noise-tolerant learning, the parity problem, and the statistical query model

<jats:p> We describe a slightly subexponential time algorithm for learning parity functions in the presence of random classification noise, a problem closely related to several cryptographic and coding problems. Our algorithm runs in polynomial time for the case of parity functions that depend on only the first <jats:italic>O</jats:italic> (log <jats:italic>n</jats:italic> log log <jats:italic>n</jats:italic> ) bits of input, which provides the first known instance of an efficient noise-tolerant algorithm for a concept class that is not learnable in the Statistical Query model of Kearns [1998]. Thus, we demonstrate that the set of problems learnable in the statistical query model is a strict subset of those problems learnable in the presence of noise in the PAC model.In coding-theory terms, what we give is a poly( <jats:italic>n</jats:italic> )-time algorithm for decoding linear <jats:italic>k</jats:italic> × <jats:italic>n</jats:italic> codes in the presence of random noise for the case of <jats:italic>k</jats:italic> = <jats:italic>c</jats:italic> log <jats:italic>n</jats:italic> log log <jats:italic>n</jats:italic> for some <jats:italic>c</jats:italic> > 0. (The case of <jats:italic>k</jats:italic> = <jats:italic>O</jats:italic> (log <jats:italic>n</jats:italic> ) is trivial since one can just individually check each of the 2 <jats:sup> <jats:italic>k</jats:italic> </jats:sup> possible messages and choose the one that yields the closest codeword.)A natural extension of the statistical query model is to allow queries about statistical properties that involve <jats:italic>t</jats:italic> -tuples of examples, as opposed to just single examples. The second result of this article is to show that any class of functions learnable (strongly or weakly) with <jats:italic>t</jats:italic> -wise queries for <jats:italic>t</jats:italic> = <jats:italic>O</jats:italic> (log <jats:italic>n</jats:italic> ) is also weakly learnable with standard unary queries. Hence, this natural extension to the statistical query model does not increase the set of weakly learnable functions. </jats:p>