The Power of Localization for Efficiently Learning Linear Separators
  with Noise
  We introduce a new approach for designing computationally efficient learning
algorithms that are tolerant to noise, and demonstrate its effectiveness by
designing algorithms with improved noise tolerance guarantees for learning
linear separators.
  We consider both the malicious noise model and the adversarial label noise
model. For malicious noise, where the adversary can corrupt both the label and
the features, we provide a polynomial-time algorithm for learning linear
separators in $\Re^d$ under isotropic log-concave distributions that can
tolerate a nearly information-theoretically optimal noise rate of $\eta =
\Omega(\epsilon)$. For the adversarial label noise model, where the
distribution over the feature vectors is unchanged, and the overall probability
of a noisy label is constrained to be at most $\eta$, we also give a
polynomial-time algorithm for learning linear separators in $\Re^d$ under
isotropic log-concave distributions that can handle a noise rate of $\eta =
\Omega\left(\epsilon\right)$.
  We show that, in the active learning model, our algorithms achieve a label
complexity whose dependence on the error parameter $\epsilon$ is
polylogarithmic. This provides the first polynomial-time active learning
algorithm for learning linear separators in the presence of malicious noise or
adversarial label noise.
