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 型不等式和对错误噪声模型的推广。

采用恶意噪声的半空间样本最优 PAC 学习

Sample-Optimal PAC Learning of Halfspaces with Malicious Noise

We study the problem of agnostically learning homogeneous halfspaces in the
distribution-specific PAC model. For a broad family of structured
distributions, including log-concave distributions, we show that non-convex SGD
efficiently converges to a solution with misclassification error
$O(\opt)+\eps$, where $\opt$ is the misclassification error of the best-fitting
halfspace. In sharp contrast, we show that optimizing any convex surrogate
inherently leads to misclassification error of $\omega(\opt)$, even under
Gaussian marginals.

研究学习同质半空间的非说服学派问题，证明对于一类结构化分布，包括对数凹分布，在误分类误差 O（opt）+eps 下，非凸 SGD 有效地收敛到解决方案。相比之下，证明优化任何凸代理本质上会导致 ω（opt）的误分类误差，即使在高斯边际分布下。