Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Evolvability

In this paper, we revisit the problem of distribution-independently learning halfspaces under Massart noise with rate . Recent work [DGT19] resolved a longstanding problem in this model of efficiently learning to error + for any >0, by giving an improper learner that partitions space into poly(d, 1/) regions. Here we give a much simpler algorithm and settle a number of outstanding open questions: (1) We give the first proper learner for Massart halfspaces that achieves + .