Title:The Power of Localization for Efficiently Learning Linear Separators with Noise

Abstract:We introduce a new approach for designing computationally efficient learning algorithms that are tolerant to noise, one of the most fundamental problems in learning theory. We demonstrate the effectiveness of our approach by designing algorithms with improved noise tolerance guarantees for learning linear separators, the most widely studied and used concept class in machine learning.
We consider two of the most challenging noise models studied in learning theory, the malicious noise model of Valiant and the adversarial label noise model of Kearns, Schapire, and Sellie. For malicious noise, where the adversary can corrupt an $\eta$ of fraction both the label part and the feature part, we provide a polynomial-time algorithm for learning linear separators in $\Re^d$ under the uniform distribution with near information-theoretic optimal noise tolerance of $\eta = \Omega(\epsilon)$. We also get similar improvements for the adversarial label noise model. We obtain similar results for more general classes of distributions including isotropic log-concave distributions.
In addition, our algorithms achieve a label complexity whose dependence on the error parameter $\epsilon$ is {\em exponentially better} than that of any passive algorithm. This provides the first polynomial-time active learning algorithm for learning linear separators in the presence of adversarial label noise, as well as the first analysis of active learning under the challenging malicious noise model.