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

Abstract:In this paper we put forward new techniques for designing efficient algorithms for learning linear separators in the presence of noise. For the challenging malicious noise model, where an adversary may corrupt both the labels and the feature part of an \eta fraction of the examples, we give a polynomial-time algorithm for learning linear separators in R^d under the uniform distribution that can handle a noise rate of \eta = \Omega(\epsilon/\log(d/\epsilon)), which is significantly better than the previously best known results of [KKMS08,KLS09]. For the adversarial label noise model where an adversary can change the labels in a region of feature space of probability at most \eta, we give a polynomial-time algorithm for learning linear separators in R^d under the uniform distribution that can handle a noise rate of \eta = \Omega(\epsilon), improving on algorithms from [KKMS08].
Furthermore, we show that our algorithms also work in the active learning model with a label complexity whose dependence on the error parameter \epsilon is 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.
Our algorithms and analysis combine several ingredients including aggressive localization, hinge loss minimization, and a novel outlier removal procedure. Our work illustrates an unexpected use of localization techniques (previously used for obtaining better sample complexity results) in order to obtain better noise-tolerant polynomial-time algorithms.