Reliable Agnostic Learning
- Varun Kanade ,
- Adam Tauman Kalai ,
- Yishay Mansour
Proceedings of the 22nd Annual Conference on Learning Theory (COLT), 2009 |
We give efficient algorithms for learning in a model of learning with one-sided agnostic noise, such as a model of SPAM emails in which legit emails come from one set but SPAM emails may be distributed arbitrarily. The goal is to achieve an accuracy as high as possible while maintaining a near-zero rate of false positives. We show how to learn the class of DNFs using membership queries in this setting.