On the Power of Localized Perceptron for Label-Optimal Learning of
  Halfspaces with Adversarial Noise
  We study {\em online} active learning of homogeneous halfspaces in
$\mathbb{R}^d$ with adversarial noise where the overall probability of a noisy
label is constrained to be at most $\nu$. Our main contribution is a
Perceptron-like online active learning algorithm that runs in polynomial time,
and under the conditions that the marginal distribution is isotropic
log-concave and $\nu = \Omega(\epsilon)$, where $\epsilon \in (0, 1)$ is the
target error rate, our algorithm PAC learns the underlying halfspace with
near-optimal label complexity of $\tilde{O}\big(d \cdot
polylog(\frac{1}{\epsilon})\big)$ and sample complexity of
$\tilde{O}\big(\frac{d}{\epsilon} \big)$. Prior to this work, existing online
algorithms designed for tolerating the adversarial noise are subject to either
label complexity polynomial in $\frac{1}{\epsilon}$, or suboptimal noise
tolerance, or restrictive marginal distributions. With the additional prior
knowledge that the underlying halfspace is $s$-sparse, we obtain
attribute-efficient label complexity of $\tilde{O}\big( s \cdot polylog(d,
\frac{1}{\epsilon}) \big)$ and sample complexity of
$\tilde{O}\big(\frac{s}{\epsilon} \cdot polylog(d) \big)$. As an immediate
corollary, we show that under the agnostic model where no assumption is made on
the noise rate $\nu$, our active learner achieves an error rate of $O(OPT) +
\epsilon$ with the same running time and label and sample complexity, where
$OPT$ is the best possible error rate achievable by any homogeneous halfspace.
