A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise

Abstract

We study the problem of PAC learning -margin halfspaces in the presence of Massart noise. Without computational considerations, the sample complexity of this learning problem is known to be (1/(^2 )). Prior computationally efficient algorithms for the problem incur sample complexity O(1/(^4 ^3)) and achieve 0-1 error of +, where <1/2 is the upper bound on the noise rate. Recent work gave evidence of an information-computation tradeoff, suggesting that a quadratic dependence on 1/ is required for computationally efficient algorithms. Our main result is a computationally efficient learner with sample complexity (1/(^2 ^2)), nearly matching this lower bound. In addition, our algorithm is simple and practical, relying on online SGD on a carefully selected sequence of convex losses.

Tasks

Reproductions