CS Paper Radar

Fundamentals for Binary Classification Under Label Noise

Dimitrios I. Diochnos

cs.CC cs.LGstat.ML ·submitted 2026-11-19 02:11 UTC · v1
top venuetheoryhot direction

Abstract

This chapter surveys fundamental results for binary classification under label noise. Binary classification under label noise involves training models on datasets where class labels are partially incorrect, leading to degraded performance and misclassification. We distinguish poisoning attacks from noise processes and formalize random classification noise, Massart noise, and malicious classification noise within the probably approximately correct (PAC) framework. These models capture different adversarial strengths and data-generation realities. We then highlight some core ideas and representative results. In particular, we explain why random classification noise preserves the expected ordering of hypotheses and thus supports learning using the empirical risk minimization (ERM) principle, how sample complexity depends on the noise rate, and why learning algorithms often require an upper bound on the corruption level, as well as how such a bound may be estimated from data in the case of random classification noise. We also discuss computational aspects of ERM under noise and present a canonical negative result technique -- the method of induced distributions -- within the malicious noise model where the adversary has more power and may affect not only the label of an example but also the instance. We conclude with pointers to related work and a taxonomy that organizes classical label-noise models using the NCAR/NAR/NNAR lens.

Comment
59 pages, 6 figures, 3 tables. Preprint of a chapter published in the book Mathematics and Artificial Intelligence (Springer)
Journal ref
In: M. C. Golumbic and F. Hoffman (eds.), Mathematics and Artificial Intelligence, Springer, Cham, 2027, pp. 37-96
DOI
10.1007/978-3-032-39161-2_3

Closest papers

Nearest neighbours by meaning across the whole index.

A Certified Robustness Framework for Backdoor Poisoning Attacks using $f$-Divergences

cs.LG cs.CR ·2026-10-26 ·Evan Rose, Alina Oprea
similarity 0.70
Abstract · 39 pages, 3 figures, 7 tables

Machine learning systems trained on untrusted data are vulnerable to data and backdoor poisoning attacks, in which an adversary corrupts training and test samples to manipulate predictions at inference time. Randomized smoothing yields provable defenses against such attacks, but existing applications to train-time robustness are limited to specific threat models and smoothing mechanisms. We propose a general framework that allows expressing complex adversary constraints on the number of corrupted training examples, feature and label perturbation magnitudes, and test-time corruptions. Our framework randomizes inputs by combining data subsampling with feature, label and test-sample noising. We develop a composable certification procedure based on $f$-divergences that handles arbitrary combinations of threat models and noising strategies, and recovers several prior certification regimes exactly as special cases. We demonstrate our framework experimentally by certifying, for the first time, robustness under general $\ell_p$-constrained poisoning adversaries under bagging with additive Laplace, Gaussian, and Uniform noises.

0.21

When Clean Data Hurts: Learning with Monotone Corruptions Beyond Binary Classification

cs.LG stat.ML ·2026-08-20 ·Julian Asilis, Shaddin Dughmi, Chirag Pabbaraju
theory similarity 0.70
Abstract · 52 pages

Optimal learners are tailored to exploit the i.i.d.\ data assumption underlying the classic PAC model. What if an i.i.d.\ training sample were corrupted with correctly labeled examples drawn from an otherwise unrelated, even adversarial source? This model of learning with monotone adversarial corruptions was recently introduced by Larsen et al. (2026), who demonstrated that all known optimal binary learners suffer increased error rates in this setting, from $O(d / n)$ in the PAC model to $Ω(d \log(n / d) / n)$ under monotone corruption. Mehrotra (2026) proved this logarithmic factor to be necessary for binary classification, but left open the consequences of corruption for more general learning settings, such as multiclass classification and partial binary concept classes. As our primary result, we demonstrate that monotone adversaries are frighteningly more powerful in each of these settings. We exhibit a learnable multiclass problem, of DS dimension only 2, that becomes altogether unlearnable under a monotone adversary, and show an analogous result for partial binary concept classes. These results are achieved by an adaptive adversary permitted to view the original i.i.d.\ training set $S$ and to insert $b < \infty$ corrupted datapoints into $S$. In the multiclass example, the adversary need only insert a linear number $b = |S| = n$ of datapoints. We complement these impossibility results by proving that every class remains learnable when the number of adaptive additions is $o(n)$, which our previous multiclass lower bound proves to be tight. We further observe that the classic multiclass error rate of $O(d_{\mathrm{DS}} / n)$ remains achievable against adaptive adversaries restricted to a known constant budget $b = O(1)$, against semi-adaptive adversaries viewing only a $p$-fraction of $S$ for $p \in (0, 1)$, and against oblivious adversaries that cannot view $S$.

0.10

Targeted Label-Flipping and Oversampling Attacks on Federated Conditional GANs

cs.LG ·2026-08-10 ·Panav Shah, Avishek Ghosh
published similarity 0.68
Abstract · 10 pages, 8 figures, FedKDD/FedMAS 2026 - KDD Workshop

In a federated learning setup for GANs, several adversarial attacks are possible. One such attack is label flipping, in which malicious clients deliberately alter label information during local training in order to manipulate the global generator. The objective of this attack is to skew the learned generation distribution so that samples conditioned on a target label are instead mapped to a source class. In this work, we investigate the effectiveness of label flipping attacks in federated GANs through both theoretical analysis and empirical evaluation. We further consider an oversampling based variant, in which malicious clients upweight poisoned samples during local training to amplify their influence on the aggregated global model. We quantify the resulting distributional shift by computing the Kullback Leibler divergence between the clean and poisoned class conditional distributions, and show both analytically and on FEMNIST, MNIST, and CIFAR10 that the semantic damage of the attack grows linearly in the effective poisoning strength while deviation from the true target distribution grows only quadratically, making the attack effective yet difficult to detect from label agnostic metrics.

0.25

On the tradeoff between robustness and geometric accuracy in adversarial training

cs.LG math.AP ·2026-10-16 ·Rachel Morris, Ryan Murray, Kerrek Stinson
theory similarity 0.66
Abstract

For non-parametric binary classification in the presence of an adversary, we prove an optimal quantitative estimate for adversarial classifiers controlling geometric accuracy, as measured by the Hausdorff distance to the Bayes classifier, in terms or their robustness, as encoded by the adversarial budget $\varepsilon$. This rigorously shows that robust classifiers sacrifice at most $O(\sqrt{\varepsilon})$ or $O(\varepsilon)$ in accuracy, depending on the regularity of the underlying Bayes classifier. In contrast to prior work on the incompatibility of robustness and accuracy over low-complexity hypothesis classes, our work shows that high-complexity hypothesis classes allow for robust classifiers with precisely quantified accuracy. Our results apply for adversaries determined by any norm on Euclidean space and in both the infinite and finite data settings.

0.34

RAMP: Reversing Adversarial Perturbations to Strengthen Clean-Label Backdoor Attacks against Malware Detectors

cs.CR ·2026-09-23 ·Jinwen Xin, Dongni Zhang, Chenyang Wang, Jianming Fu, Ming Tang +1 more
publishedcode/data similarity 0.64
Abstract · 20 pages, 7 figures, 5 tables. Accepted at the 22nd International Conference on Information Security and Cryptology (Inscrypt 2026). Code: h…

Deep learning-based malware detectors are commonly updated by fine-tuning on newly collected samples, but this practical update pipeline also creates an attack surface for training-time backdoor attacks. In realistic crowdsourced data collection, however, strict label vetting typically restricts attackers to the clean-label setting, in which poisoned samples must retain benign labels and functionality, making effective backdoor injection substantially harder. We present a new attack perspective based on feature-space manipulation: instead of relying solely on stronger trigger designs or selecting benign samples that are naturally similar to malware, we deliberately construct benign programs whose representations shift toward the malware region before trigger injection, thereby creating stronger feature-label conflicts during training. Based on this insight, we propose RAMP, an attack enhancement method that uses a genetic algorithm to optimize reversed adversarial perturbations under black-box access and then injects them through functionality-preserving binary manipulations. Extensive experiments show that RAMP substantially improves attack effectiveness over trigger-only baselines, with especially pronounced gains at low poisoning ratios, while maintaining accuracy on clean data. Moreover, RAMP can be combined with advanced trigger designs.

0.36

Evasion Attacks: How Adversarial Noise Bypasses ML Classifiers

cs.CR cs.CLcs.LG ·2026-09-10 ·Parker Hummel, Ryne Skabo, Muhammad Abusaqer
published similarity 0.64
Abstract · Presented at the 58th Midwest Instruction and Computing Symposium (MICS 2026), Eau Claire, WI, March 27 to 28, 2026. 14 pages, 7 figures, 4 …

This paper presents a reproducible, educational study of evasion attacks in image classification and text classification. A compact convolutional network trained on MNIST reached 98.63% clean test accuracy and was evaluated under two white-box attacks. Under FGSM, accuracy fell to 60.20% at $ε$ = 0.15 and 1.72% at $ε$ = 0.30; under PGD it fell to 32.47% and 0.41%, and a bit-depth-reduction defense recovered only part of the loss. In the second experiment, DistilBERT fine-tuned on the SMS Spam Collection reached 98.75% accuracy and a 94.96% F1-score, but a controlled sequence of pre-defined perturbations (character substitutions, whitespace noise, and a benign suffix) produced only modest probability shifts in most displayed examples and no flip from spam to ham. Adversarial vulnerability is strongly modality-dependent: the MNIST experiment is a clear evasion demonstration, whereas the text experiment is a controlled robustness evaluation. Robustness must be tested empirically rather than inferred from clean accuracy.

0.37

Adversarial Robustness of Kernel Machines: A Comprehensive Analysis

cs.LG cs.AI ·2026-11-05 ·Rahul Kumar Yadav, Tunir Ghosh, Sudhendu Ahir, Parthe Pandit, Arjun Bhagoji
similarity 0.64
Abstract

Kernel machines are an important class of models in machine learning. However, the question of how robust modern kernel machines are to adversarial examples has not been studied comprehensively. In this paper, we provide a thorough empirical investigation of the adversarial robustness of kernel-based models for both binary and multiclass classification tasks, via white-box and black-box evasion attacks. We evaluate the native robustness of kernel machines, random feature classifiers, and the relatively newer Recursive Feature Machines. In addition, we provide an algorithm for approximate adversarial training of kernel machines. Our experiments on classification tasks on image and tabular datasets strongly indicate that kernel machines are natively more robust than neural networks, i.e., their performance degrades more gracefully against adversarial perturbations.

0.13

When Does Training on Synthetic Data Provably Work?

cs.LG stat.ML ·2026-10-20 ·Leroy Odunlami, Tobias Riedlinger, Hanno Gottschalk
similarity 0.63
Abstract

High-quality training data are a major bottleneck in machine learning, motivating increasing use of artificially generated data. We study when a binary classifier trained on synthetic data transfers successfully to a real distribution, under a shared conditional label distribution. First, we derive finite-sample excess-error bounds when the real covariate distribution is absolutely continuous with respect to the synthetic distribution under a controlled density ratio. Second, we study the partially and fully singular case, where the real distribution has mass outside the synthetic one. If the hypothesis class is sufficiently expressive, synthetic risk alone cannot uniformly control real-world error: a classifier can be nearly optimal on synthetic data while approaching worst-case error on the uncovered real region, even when the distributions are arbitrarily close in Wasserstein distance. For function classes where hypotheses and the log-odds of the conditional label probability are Lipschitz, we recover a bound in terms of the probability that a real sample lies outside the reach of the synthetic data, restoring a transfer guarantee even in the fully singular case. Experiments confirm this in controlled low-dimensional settings and on 32,200 images generated as counterparts to real ImageNet images by four state-of-the-art generators: an adversarial classifier reaches 0.5% error on the synthetic domain but 99.25% error on the real domain, while ordinarily trained architectures show positively correlated synthetic and real test errors. Synthetic data should be budgeted at high sample counts and models validated on real data.

0.28