Learning with queries corrupted by classification noise

Kearns introduced the ‘statistical query’ model as a general method for producing learning algorithms which are robust against classification noise. We extend this approach in several ways in order to tackle algorithms that use ‘membership queries’, focusing on the more stringent model of ‘persistent noise’. The main ingredients in the general analysis are: 1. Smallness of dimension of the classes of both the target and the queries. 2. Independence of the noise variables. Persistence restricts independence, forcing repeated invocation of the same point x to give the same label. We apply the general analysis to get a noise-robust version of Jackson's Harmonic Sieve, which learns DNF under the uniform distribution. This corrects an error in his earlier analysis of noise tolerant DNF learning.