Non-Convex SGD Learns Halfspaces with Adversarial Label Noise

Abstract

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.

References in corpus (2)

• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals
• Approximation Schemes for ReLU Regression

Cited by in corpus (2)

• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise
• The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals