Lethal Dose Conjecture on Data Poisoning
Lethal Dose Conjecture on Data Poisoning
复制标题
DOI：
10.48550/arxiv.2208.03309
复制
发表时间：
2022-08
期刊：
影响因子：
--
通讯作者：
Wenxiao Wang;Alexander Levine;S. Feizi
中科院分区：
文献类型：
--
作者：
Wenxiao Wang;Alexander Levine;S. Feizi
数据中毒认为对手为了恶意目的而扭曲机器学习算法的训练集。在这项工作中，我们揭示了一个关于数据中毒的基本原理的猜想，我们称之为致命剂量猜想。该猜想指出：如果需要$n$干净的训练样本来进行准确的预测，那么在大小为$N$的训练集中，在确保准确性的同时，只能容忍$\Theta（N/n）$中毒的样本。从理论上讲，我们在多个案例中验证了这一猜想。我们还提供了一个更一般的角度来看，这一猜想通过分布歧视。深度分区聚合（DPA）及其扩展，有限聚合（FA）是最近用于可证明的数据中毒防御的方法，其中它们通过使用给定学习器从训练集的不同子集训练的许多基础模型的多数投票进行预测。这个猜想意味着DPA和FA都是（渐近）最优的--如果我们有最有效的数据学习器，它们可以把它变成最强大的数据中毒防御之一。这概述了一种实用的方法，通过寻找数据高效的学习者来开发更强大的防御中毒。从经验上讲，作为概念证明，我们表明，通过简单地使用不同的数据增强的基础学习者，我们可以分别增加一倍和三倍的认证的鲁棒性DPA CIFAR-10和GTSRB不牺牲准确性。
Data poisoning considers an adversary that distorts the training set of machine learning algorithms for malicious purposes. In this work, we bring to light one conjecture regarding the fundamentals of data poisoning, which we call the Lethal Dose Conjecture. The conjecture states: If $n$ clean training samples are needed for accurate predictions, then in a size-$N$ training set, only $\Theta(N/n)$ poisoned samples can be tolerated while ensuring accuracy. Theoretically, we verify this conjecture in multiple cases. We also offer a more general perspective of this conjecture through distribution discrimination. Deep Partition Aggregation (DPA) and its extension, Finite Aggregation (FA) are recent approaches for provable defenses against data poisoning, where they predict through the majority vote of many base models trained from different subsets of training set using a given learner. The conjecture implies that both DPA and FA are (asymptotically) optimal -- if we have the most data-efficient learner, they can turn it into one of the most robust defenses against data poisoning. This outlines a practical approach to developing stronger defenses against poisoning via finding data-efficient learners. Empirically, as a proof of concept, we show that by simply using different data augmentations for base learners, we can respectively double and triple the certified robustness of DPA on CIFAR-10 and GTSRB without sacrificing accuracy.