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.

本研究提出了一种新的方法来设计计算效率高、能够容忍噪声的学习算法，并通过设计具有改善噪声容忍度的线性分离器学习算法来证明其有效性。在恶意噪声模型和对抗标签噪声模型方面展开讨论，并为这些模型提供了多项式时间算法，以在各自的噪声下学习线性分类器。在主动学习模型下，算法实现标签复杂度对于误差参数的对数对数依赖。