Search papers, labs, and topics across Lattice.
This paper addresses the challenge of learning drifting halfspaces in the presence of Massart noise, where the target concept can change over time. The authors present a computationally efficient learner that achieves a prediction error of \(η + \tilde O(Δ^{1/3}/γ)\), significantly improving upon previous methods in the realizable setting. Additionally, they establish a lower bound demonstrating that while optimal error scales with \(Δ^{1/2}\), achieving \(Δ^{1/3}\)-scaling is a fundamental limitation for low-degree polynomial tests, highlighting the complexity of the learning problem.
Achieving a prediction error that scales with \(Δ^{1/3}\) reveals a surprising limitation in learning dynamics under Massart noise, challenging previous assumptions about optimal performance.
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 $η+ \tilde O(Δ^{1/3}/γ)$, where $η$ upper bounds the Massart noise rate, $Δ$ is the drift rate, and $γ$ 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 $Δ^{1/2}$, we prove that $Δ^{1/3}$-scaling is unavoidable for low-degree polynomial tests, even in the special case of random classification noise.
