当干净数据有害：超越二元分类的单调腐败学习

arXiv cs.LG 论文
machine-learning adversarial-corruption binary-classification multiclass-classification pac-model ds-dimension theoretical-analysis

摘要

本文证明，单调对抗腐败可以使某些多类和部分二元分类问题变得不可学习，提供了腐败预算的紧界，并扩展了先前关于二元分类的结果。

arXiv:2608.20480v1 Announce Type: new 摘要：最优学习器旨在利用经典PAC模型下的i.i.d.数据假设。如果一个i.i.d.训练样本被来自另一个无关甚至对抗来源的正确标记样本污染会怎样？这种单调对抗腐败的学习模型最近由Larsen等人（2026）引入，他们证明了所有已知的最优二元学习器在这种设置下误差率会增加，从PAC模型中的$O(d / n)$到单调腐败下的$\Omega (d \log(n / d) / n)$。Mehrotra（2026）证明了这个对数因子对于二元分类是必要的，但对于更一般的学习设置，如多类分类和部分二元概念类，腐败的后果仍然开放。 作为我们的主要结果，我们证明单调对抗者在每个这些设置中都强大得惊人。我们展示了一个可学习的多类问题，DS维度仅为2，在单调对抗者下变得完全不可学习，并展示了部分二元概念类的类似结果。这些结果通过一个自适应对抗者实现，该对抗者被允许查看原始i.i.d.训练集$S$并将$b < \infty$个腐败数据点插入$S$。在多类例子中，对抗者只需要插入线性数量$b = |S| = n$的数据点。 我们通过证明当自适应添加的数量为$o(n)$时，每个类仍然是可学习的，来补充这些不可能结果，我们先前的多类下界证明这是紧的。我们进一步观察到，经典多类误差率$O(d_{\mathrm{DS}} / n)$在面对限制为已知常数预算$b = O(1)$的自适应对抗者、仅查看$S$的$p$分数（$p \in (0, 1)$）的半自适应对抗者、以及无法查看$S$的无知对抗者时仍然是可实现的。
查看原文
查看缓存全文

缓存时间: 2026/08/24 04:30 

# 当干净数据造成伤害：超越二分类的单调腐蚀学习
来源：https://arxiv.org/abs/2608.20480
查看PDF (https://arxiv.org/pdf/2608.20480)

> 摘要：最优学习器专门用于利用经典PAC模型所基于的独立同分布(i.i.d.)数据假设。若独立同分布的训练样本被来自其他无关（甚至对抗性）源的正确标注样本所污染会如何？这种单调对抗腐蚀学习模型最近由Larsen等人（2026）提出，他们证明所有已知的最优二分类学习器在此设定下误差率均会增加——从PAC模型中的$O(d/n)$提升至单调腐蚀下的$\Omega(d\log(n/d)/n)$。Mehrotra（2026）证明该对数因子对二分类是必要的，但未明确腐蚀对更广义学习场景（如多分类和部分二元概念类）的影响。作为主要结论，我们证明单调对抗者在这些场景中具有惊人的强大能力。我们展示了一个仅DS维度为2的可学习多分类问题，在单调对抗下完全不可学习，并对部分二元概念类得出类似结论。这些结果通过允许观察原始独立同分布训练集$S$并插入$b < \infty$个腐蚀数据点的自适应对抗者实现。在多分类示例中，对抗者仅需插入线性数量$b = \|S\| = n$个数据点。我们通过证明当自适应添加数量为$o(n)$时所有概念类仍可学习，来补充这些不可能性结果——先前的多分类下界证明该界限是紧的。我们进一步观察到：经典多分类错误率$O(d_{\mathrm{DS}}/n)$在面对受限于已知常数预算$b=O(1)$的自适应对抗者、仅观察$p \in (0, 1)$比例$S$的半自适应对抗者，以及无法观察$S$的非适应性对抗者时仍然可达。

## 提交历史
来自：Julian Asilis [查看邮件 (https://arxiv.org/show-email/4eb63d7e/2608.20480)] **[v1]** 2026年8月20日 星期四 18:10:54 UTC (50 KB)

相似文章

揭示拜占庭鲁棒性下隐私对泛化的非单调影响

arXiv cs.LG

本文揭示了在拜占庭鲁棒分布式学习中隐私对泛化误差的非单调影响：在高噪声（强隐私）区域，增加隐私会降低泛化误差；而在低噪声（弱隐私）区域，增加隐私则会恶化泛化效果。

使用受控损坏对实例相关标签噪声进行基准测试

arXiv cs.LG

介绍了CILN，一种通过受控输入损坏生成实例相关标签噪声基准的框架，能够显式控制模糊性的来源和严重程度。实验表明，它能够产生逼真的噪声结构，并揭示了流行的噪声标签学习方法中的失败模式。