The Power of Localization for Efficiently Learning Linear Separators with Malicious Noise.
Pranjal Awasthi, Maria-Florina Balcan, Philip M. Long · arXiv (Cornell University) · 2013
In this paper we put forward new techniques for designing efficient algorithms for learning linear separators in the challenging malicious noise model, where an adversary may corrupt both the labels and the feature part of an η fraction of the examples. Our main result is a polynomial-time algorithm for learning linear separators in ℜd under the uniform distribution that can handle a noise rate of η = O