We study efficient PAC learning of homogeneous halfspaces in $\mathbb{R}^d$
in the presence of malicious noise of Valiant (1985). This is a challenging
noise model and only until recently has near-optimal noise tolerance bound been
established under the mild condition that the unlabeled data distribution is
isotropic log-concave. However, it remains unsettled how to obtain the optimal
sample complexity simultaneously. In this work, we present a new analysis for
the algorithm of Awasthi et al. (2017) and show that it essentially achieves
the near-optimal sample complexity bound of $\tilde{O}(d)$, improving the best
known result of $\tilde{O}(d^2)$. Our main ingredient is a novel incorporation
of a matrix Chernoff-type inequality to bound the spectrum of an empirical
covariance matrix for well-behaved distributions, in conjunction with a careful
exploration of the localization schemes of Awasthi et al. (2017). We further
extend the algorithm and analysis to the more general and stronger nasty noise
model of Bshouty et al. (2002), showing that it is still possible to achieve
near-optimal noise tolerance and sample complexity in polynomial time.

本文提出一种能够在存在恶意噪声的条件下有效学习欧氏空间中均匀半空间的 PAC 算法，该算法框架下的样本复杂度接近最优，主要用到了矩阵 Chernoff 型不等式和对错误噪声模型的推广。