Efficiently Learning Drifting Halfspaces with Massart Noise

We study the problem of learning a drifting concept in the presence of Massart noise. In this framework, an online learner has access to a history of independent samples whose labels are noisy versions of a target concept that may change from round to round. The goal is to output, in each round, a hypothesis with small prediction error. We study the complexity of this learning problem for the fundamental class of margin-separable linear classifiers (halfspaces). On the positive side, we give a computationally efficient learner achieving error $\eta + \tilde O(\Delta^{1/3}/\gamma)$, where $\eta$ upper bounds the Massart noise rate, $\Delta$ is the drift rate, and $\gamma$ is the margin. Interestingly, in the realizable setting, an adaptation of our techniques yields an efficient learner with an improved error rate over prior work. On the lower-bound side, we provide formal evidence of an information-computation tradeoff, strongly suggesting that our algorithm's performance is essentially optimal. Specifically, while the information-theoretically optimal error scales with $\Delta^{1/2}$, we prove that $\Delta^{1/3}$-scaling is unavoidable for low-degree polynomial tests, even in the special case of random classification noise.

This paper studies the problem of learning drifting halfspaces with Massart noise. We provide efficient learning algorithms as well as computational complexity results for the problem