Efficiently Learning Drifting Halfspaces with Massart Noise

arXiv:2606.11149v1 Announce Type: new Abstract: 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 + ilde 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.

Source: arXiv cs.LG | 2026-06-10