论文标题
非Convex SGD学习具有对抗标签噪声的半空间
Non-Convex SGD Learns Halfspaces with Adversarial Label Noise
论文作者
论文摘要
我们研究了分布特异性PAC模型中不可知的同质半空间的问题。对于包括Log-Concave分布在内的广泛结构化分布的家庭，我们表明，非convex SGD有效收敛到具有错误分类错误$ O（\ opt）+\ eps $的解决方案，其中$ \ opt $是最适合拟合半空间的错误分类错误。相比之下，我们表明，即使在高斯边际边际下，也固有地优化任何凸构代替代物会导致$ω（\ opt）$的错误分类误差。
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 $ω(\opt)$, even under Gaussian marginals.
