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. We demonstrate the effectiveness of our approach by designing algorithms with improved noise tolerance guarantees for learning linear separators.
We consider 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 malicious noise model.