It has been a long-standing problem to efficiently learn a halfspace using as
few labels as possible in the presence of noise. In this work, we propose an
efficient Perceptron-based algorithm for actively learning homogeneous
halfspaces under the uniform distribution over the unit sphere. Under the
bounded noise condition~\cite{MN06}, where each label is flipped with
probability at most $\eta < \frac 1 2$, our algorithm achieves a near-optimal
label complexity of
$\tilde{O}\left(\frac{d}{(1-2\eta)^2}\ln\frac{1}{\epsilon}\right)$ in time
$\tilde{O}\left(\frac{d^2}{\epsilon(1-2\eta)^3}\right)$. Under the adversarial
noise condition~\cite{ABL14, KLS09, KKMS08}, where at most a $\tilde
\Omega(\epsilon)$ fraction of labels can be flipped, our algorithm achieves a
near-optimal label complexity of $\tilde{O}\left(d\ln\frac{1}{\epsilon}\right)$
in time $\tilde{O}\left(\frac{d^2}{\epsilon}\right)$. Furthermore, we show that
our active learning algorithm can be converted to an efficient passive learning
algorithm that has near-optimal sample complexities with respect to $\epsilon$
and $d$.

本文提出了一种半空间主动学习算法，能够在存在噪声和尽可能少的标签情况下，有效地学习均匀分布在单位球上的均匀半空间，并证明其在两种噪声情况下均达到了近似最优标签复杂度。