Uniform-Distribution Attribute Noise Learnability

We study the problem of PAC-learning Boolean functions with random attribute noise under the uniform distribution. First, we define a noisy distance measure for function classes and show that if this measure is small for a class C and an attribute noise distribution D then C is not learnable with respect to the uniform distribution in the presence of noise generated according to D. The noisy distance measure is then characterized in terms of Fourier properties of the function class. We use this characterization to show that the class of all parity functions is not learnable for any but very concentrated noise distributions D. On the other hand, we show that if C is learnable with respect to uniform using a standard Fourier-based learning technique, then C is learnable with time and sample complexity also determined by the noisy distance. In fact, we show that this style algorithm is the best possible for learning in the presence of attribute noise. 1 INTRODUCTION The problem of attri..