On agnostic boosting and parity learning

The motivating problem is agnostically learning parity functions, i.e., parity with arbitrary or adversarial noise. Specifically, given random labeled examples from an *arbitrary* distribution, we would like to produce an hypothesis whose accuracy nearly matches the accuracy of the best parity function. Our algorithm runs in time 2 O(n/log n) , which matches the best known for the easier cases of learning parities with random classification noise (Blum et al, 2003) and for agnostically learning parities over the uniform distribution on inputs (Feldman et al, 2006).

Authors

• Adam Tauman Kalai
• Yishay Mansour
• Elad Verbin

Keywords

• agnostic learning
• agnostic boosting
• sub-exponential algorithms
• learning parity with noise