Efficiently Learning Drifting Halfspaces with Massart Noise

• URL: http://arxiv.org/abs/2606.11149v1
• Date: Tue, 09 Jun 2026 17:35:18 GMT
• Title: Efficiently Learning Drifting Halfspaces with Massart Noise
• Abstract summary: We study the problem of learning a drifting concept in the presence of Massart noise.<n>In this framework, an online learner has access to a history of independent samples.<n>The goal is to output, in each round, a hypothesis with small prediction error.
• Score: 50.4331323695175
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 $η+ \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.

Related papers

• Optimal Learning Under Tsybakov Noise [31.74405851825694]
  We design a learning algorithm that outputs a hypothesis having low error competitive to $h*$ with high probability.<n>Our technique shares a conceptual foundation with several recent advances in non-realizable learning.
  arXiv  Detail & Related papers  (2026-08-09T02:20:51Z)
• Online Set Learning from Precision and Recall Feedback [60.00180898830079]
  We consider the problem of learning an unknown subset $N_texttarget$ of a domain in an online setting.<n>This simple online set learning problem abstracts a variety of learning scenarios with precision- and recall-type feedback.<n>We show that a hypothesis class is learnable in this setting if and only if it has finite Vapnik-Chervonenkis dimension.
  arXiv  Detail & Related papers  (2026-05-10T14:28:05Z)
• Attribute-Efficient PAC Learning of Sparse Halfspaces with Constant Malicious Noise Rate [10.550885570889527]
  Attribute-efficient learning of sparse halfspaces has been a fundamental problem in machine learning theory.<n>In this paper, we consider that there exists a constant amount of malicious noise in the data and the goal is to learn an underlying $s$-sparse halfspace.<n>Under such conditions, we show that attribute-efficiency can be achieved by simple variants to existing hinge loss minimization programs.
  arXiv  Detail & Related papers  (2025-05-27T17:02:28Z)
• Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random [17.56894435702055]
  We study the problem of PAC learning $gamma$-margin halfspaces with Massart noise.<n>We propose a simple proper learning algorithm, the Perspectron, that has sample complexity $widetildeO((epsilongamma)-2)$.
  arXiv  Detail & Related papers  (2025-01-16T21:46:53Z)
• Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
  We study the complexity of PAC learning halfspaces in the presence of Massart noise. We show that no-time Massart halfspace learners can achieve error better than $Omega(eta)$, even if the optimal 0-1 error is small.
  arXiv  Detail & Related papers  (2022-07-28T17:50:53Z)
• Boosting in the Presence of Massart Noise [49.72128048499074]
  We study the problem of boosting the accuracy of a weak learner in the (distribution-independent) PAC model with Massart noise. Our main result is the first computationally efficient boosting algorithm in the presence of Massart noise. As a simple application of our positive result, we give first efficient Massart learner for unions of high-dimensional rectangles.
  arXiv  Detail & Related papers  (2021-06-14T22:21:25Z)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  We study the complexity of PAC learning halfspaces in the presence of Massart (bounded) noise. We show that there an exponential gap between the information-theoretically optimal error and the best error that can be achieved by a SQ algorithm.
  arXiv  Detail & Related papers  (2020-12-17T16:43:11Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  We study the learnability of halfspaces in the presence of Tsybakov noise. We give an algorithm that achieves misclassification error $epsilon$ with respect to the true halfspace.
  arXiv  Detail & Related papers  (2020-06-11T14:25:02Z)
• Towards Deep Learning Models Resistant to Large Perturbations [0.0]
  Adversarial robustness has proven to be a required property of machine learning algorithms. We show that the well-established algorithm called "adversarial training" fails to train a deep neural network given a large, but reasonable, perturbation magnitude.
  arXiv  Detail & Related papers  (2020-03-30T12:03:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.