Is nasty noise actually harder than malicious noise?

• URL: http://arxiv.org/abs/2511.09763v1
• Date: Fri, 14 Nov 2025 01:08:31 GMT
• Title: Is nasty noise actually harder than malicious noise?
• Authors: Guy Blanc, Yizhi Huang, Tal Malkin, Rocco A. Servedio,
• Abstract summary: We consider the relative abilities and limitations of computationally efficient algorithms for learning in the presence of noise.<n>For distribution-independent learning, we prove a strong equivalence between the two noise models.<n>We show that for these algorithms, malicious noise and nasty noise are equivalent up to a factor of two in the noise rate.
• Score: 5.887031992513966
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We consider the relative abilities and limitations of computationally efficient algorithms for learning in the presence of noise, under two well-studied and challenging adversarial noise models for learning Boolean functions: malicious noise, in which an adversary can arbitrarily corrupt a random subset of examples given to the learner; and nasty noise, in which an adversary can arbitrarily corrupt an adversarially chosen subset of examples given to the learner. We consider both the distribution-independent and fixed-distribution settings. Our main results highlight a dramatic difference between these two settings: For distribution-independent learning, we prove a strong equivalence between the two noise models: If a class ${\cal C}$ of functions is efficiently learnable in the presence of $η$-rate malicious noise, then it is also efficiently learnable in the presence of $η$-rate nasty noise. In sharp contrast, for the fixed-distribution setting we show an arbitrarily large separation: Under a standard cryptographic assumption, for any arbitrarily large value $r$ there exists a concept class for which there is a ratio of $r$ between the rate $η_{malicious}$ of malicious noise that polynomial-time learning algorithms can tolerate, versus the rate $η_{nasty}$ of nasty noise that such learning algorithms can tolerate. To offset the negative result for the fixed-distribution setting, we define a broad and natural class of algorithms, namely those that ignore contradictory examples (ICE). We show that for these algorithms, malicious noise and nasty noise are equivalent up to a factor of two in the noise rate: Any efficient ICE learner that succeeds with $η$-rate malicious noise can be converted to an efficient learner that succeeds with $η/2$-rate nasty noise. We further show that the above factor of two is necessary, again under a standard cryptographic assumption.

Related papers

• Enhance Vision-Language Alignment with Noise [59.2608298578913]
  We investigate whether the frozen model can be fine-tuned by customized noise.<n>We propose Positive-incentive Noise (PiNI) which can fine-tune CLIP via injecting noise into both visual and text encoders.
  arXiv  Detail & Related papers  (2024-12-14T12:58:15Z)
• Learning Constant-Depth Circuits in Malicious Noise Models [9.036777309376697]
  We prove Linial, Mansour, and Nisan's quasipolynomial-time algorithm for learning constant-depth circuits. We attain the best possible dependence on the noise rate and succeed in the harshest possible noise model.
  arXiv  Detail & Related papers  (2024-11-06T00:19:58Z)
• Data Augmentation of Contrastive Learning is Estimating Positive-incentive Noise [54.24688963649581]
  We scientifically investigate the connection between contrastive learning and $pi$-noise. Inspired by the idea of Positive-incentive Noise (Pi-Noise or $pi$-Noise) that aims at learning the reliable noise beneficial to tasks, we develop a $pi$-noise generator.
  arXiv  Detail & Related papers  (2024-08-19T12:07:42Z)
• Multiclass Learning from Noisy Labels for Non-decomposable Performance Measures [15.358504449550013]
  We design algorithms to learn from noisy labels for two broad classes of non-decomposable performance measures. In both cases, we develop noise-corrected versions of the algorithms under the widely studied class-conditional noise models. Our experiments demonstrate the effectiveness of our algorithms in handling label noise.
  arXiv  Detail & Related papers  (2024-02-01T23:03:53Z)
• Certified Adversarial Robustness Within Multiple Perturbation Bounds [38.3813286696956]
  Randomized smoothing (RS) is a well known certified defense against adversarial attacks. In this work, we aim to improve the certified adversarial robustness against multiple perturbation bounds simultaneously.
  arXiv  Detail & Related papers  (2023-04-20T16:42:44Z)
• Identifying Hard Noise in Long-Tailed Sample Distribution [71.8462682319137]
  We introduce Noisy Long-Tailed Classification (NLT)<n>Most de-noising methods fail to identify the hard noises.<n>We design an iterative noisy learning framework called Hard-to-Easy (H2E)
  arXiv  Detail & Related papers  (2022-07-27T09:03:03Z)
• The Optimal Noise in Noise-Contrastive Learning Is Not What You Think [80.07065346699005]
  We show that deviating from this assumption can actually lead to better statistical estimators. In particular, the optimal noise distribution is different from the data's and even from a different family.
  arXiv  Detail & Related papers  (2022-03-02T13:59:20Z)
• Learning with Group Noise [106.56780716961732]
  We propose a novel Max-Matching method for learning with group noise. The performance on arange of real-world datasets in the area of several learning paradigms demonstrates the effectiveness of Max-Matching.
  arXiv  Detail & Related papers  (2021-03-17T06:57:10Z)
• 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)
• Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerance [21.76197397540397]
  This paper is concerned with computationally efficient learning of homogeneous sparse halfspaces in $mathbbRd$ under noise. We show that the sample complexity is $tildeObig(frac 1 epsilon s2 log5 d big)$ which also enjoys the attribute efficiency.
  arXiv  Detail & Related papers  (2020-06-06T04:57:39Z)

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.