Non-Convex SGD Learns Halfspaces with Adversarial Label Noise
This addresses a fundamental limitation in robust machine learning for classification tasks, providing a non-incremental breakthrough by overcoming inherent barriers of convex methods.
The paper tackles the problem of learning halfspaces with adversarial label noise, showing that non-convex SGD achieves misclassification error O(opt) + ε for structured distributions like log-concave ones, while convex surrogates inherently lead to error ω(opt) even under Gaussian marginals.
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.