Lethal Dose Conjecture on Data Poisoning
Authors: Wenxiao Wang
Alexander Levine
Soheil Feizi
Venue: NeurIPS 2022 Accept (2022)
Keywords: data poisoning
robustness
theory
security

Abstract: 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. 

Lethal Dose Conjecture on Data Poisoning
Wenxiao Wang, Alexander Levine and Soheil Feizi
Department of Computer Science
University of Maryland
College Park, MD 20742
{wwx, alevine0, sfeizi) 0umd, edu
Abstract
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 needed for accurate predictions, then a size-N training set, only ((Nnn) poisoned samples be tolerated while ensuring accuracy. Theoretically, 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-ir we have the most data-efficient learner, they can turn it into one of the most robust defenses against data poisoning. This outlines practical approach developing stronger defenses against poisoning via finding data- tata-efficient learners. Empirically, as 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 10 and GTSRB without sacrificing accuracy.
verify this conjecture
Introduction
With the increasing popularity of machine learning and especially deep learning, concerns about the reliability of training data have also increased: typically. because of the availability of data, many training samples have to be collected from users, internet websites, other potentially malicious sources for satisfying utilities. This motivates the development of the data poisoning threat model, which focuses on the reliability of models trained from adversarially distorted data [3].
Data poisoning a class of training-time adversarial attacks: The adversary is given the ability to insert and remove bounded number of training samples to manipulate the behavior (e.g. predictions for some target samples) of models trained using the resulted, poisoned dataset. Models trained from the poisoned dataset are referred to poisoned models and the allowed number of insertion and removal is the attack size.
To challenge the reliability of poisoned models, many variants of poisoning attacks have been proposed, including triggerless attacks [28] 37 I [2], which do not modify target samples, and backdoor attacks [5] 32 27). which modify them. In addition, in cases where the adversary can achieve its goal with a negliggligi probability by doing nothing, a theoretical study 23 discovers a provable attack replacing Ö(VN) samples in a size-N training set. Meanwhile, defenses against
data poisoning are also emerging, including detection- based defenses [30 10
25
31 33), trying
to identify poisoned samples, and training-basee defenses [35] robustifying models trained from poisoned data.
22
aiming at
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

In this work, we target the fundamentals of data poisoning and ask:
What amount of poisoned samples will make specific task impossible?
The answer we propose is the following conjecture, characterizing the lethal dose for a specific task:
Lethal Dose Conjecture (informal)
For a given task, if the most data-efficient learner takes at least clean samples for accurate prediction, then when a potentially poisoned, size-N training set given, any defense can tolerate at most (NV/) poisoned samples while ensuring accuracy.
Notably, the conjecture considers an adversary who 1. knows the underlying distribution of clean data and 2. can both insert and remove samples when conducting data poisoning. The formal statement of the conjecture is in Section 1. We prove the conjecture in multiple settings including Gaussian classifications and offer general perspective through distribution discrimination.
Theoretically, the conjecture relates learning from poisoned data with learning from clean data, reducing robustness against data poisoning to data efficiency and offering us much more intuitive way estimate the upper bound for robustness: To find out how many poisoned samples are tolerable, one can now instead search for data-efficient learners.
In addition, the conjecture implies that Deep Partition Aggregation (DPA) 20 and its extension, Finite Aggregation (FA) (34] are (asymptotically) optimal: DPA and FA are recent approaches for provable defenses against data poisoning, predicting through the majority vote of many base models trained from different subsets of training set using given base learner. If we have the most data-efficient learner, DPA and FA can turn into defenses against data poisoning that approach the upper bound of robustness indicated by Lethal Dose Conjecture within a constant factor.
The optimality of DPA and FA (indicated by the conjecture) outlines practical approach to developing stronger defenses by finding more data-efficient learners. As a proof of concept, we show on CIFAR- 10 and GTSRB that by simply using different data augmentations to improve the data efficiency of base learners, the certified robustness of DPA can be respectively doubled and tripled without sacrificing accuracy, highlighting the potential of this practical approach.
Another implication from the conjecture is that a stronger defense than DPA (which is asymptotically optimal assuming the conjecture) implies the existence of more data-efficient learner. As an example, we show how to derive learner from the nearest neighbors defenses (16), which are more robust than DPA in their evaluation. With the derived learner, DPA offers similar robustness to their defenses.
In summary. our contributions are as follows:
We propose Lethal Dose Conjecture, characterizing the largest amount of poisoned samples any defense can tolerate for a specific task;
We prove the conjecture in multiples cases including Isotropic Gaussian classifications;
We offer a general perspective supporting the conjecture through distribution discrimination;
We showcase how more data-efficient learners can be optimally (assuming the conjecture) transferred into stronger defenses: By simply using different augmentations get more data- efficient base learners, we double and triple the certified robustness of DPA respectively on CIFAR- 10 and GTSRB without sacrificing accuracy;
We illustrate how a learner can be derived from the nearest neighbors defenses [16], which, in their evaluation, are much more robust than DPA (which asymptotically optimal assuming the conjecture--Give the derived learner, DPA transfers it to a defense with comparable robustness the nearest neighbors defenses.
2 Related Work
DPA 20 and FA [34] we discuss in Section 7 are pointwise certified defenses against data poisoning. where the prediction on every sample guaranteed unchanged within a certain attack size. Jia et al. 17 and Chen et al. 4 offer similar but probabilistic pointwise guarantees. Meanwhile, Weber et al.

---

35
and Rosenfeld et al. [26] use randomized smoothing to provably defend against backdoor attacks
and label- tlippiig attacks [26]. Diakonikolas al. [TO] provably approximates clean models assuming certain clean data distributions, Awasthi et al. [2] and Balcan et al. 3 provably learn linear
351
separators over isotropic log-concave distributions under data poisoning.
Prior to Lethal Dose Conjecture, Gao et al. [T] use the framework of PAC learning to explore how the number of poisoned samples and the size of the training set can affect the threat of data poisoning attacks. Let N be the size of the training set and m be the number of poisoned samples. Their main results suggest that when the number of poisoned samples m scales sublinearly with the size of training set N (i.e. m o(N) or m/N - 0), the poisoning attack will be defendable. Meanwhile, our Lethal Dose Conjecture offers more accurate characterization: The threshold for when poisoning attacks can be too strong to be defended is when m/N = (2(1/n), where is the number of samples needed by the most data-efficient learners achieve accurate predictions.
3 Background and Notation
Classification Problem: A classification problem X,Y P,F) consists of: X-thhe space of inputs; Yhe space of labels; Ω the space of all labeled samples X x P- distribution over Q that is unknown to learners; and F-e set of plausible learners.
Learner: For a classification problem (X, Y, P,F), learner f E F is (stochastic) function f: .22 + mapping (finite) training set to a classifier, where C' denotes the set of all classifiers. A classifier is a (stochastic) function from the input space X to the label set Y, where the outputs are called predictions. For a learner f. fo denotes the classifier corresponding to a training set D Q and (z) denotes the prediction of the classifier for input X.
In clean learning, given classification problem Y,, and training set size n. the learner has access to a clean training set containing n i.i.d samples from P and thus the resulting classifier can be denoted as fD. where D, p" is the size-n training set.
Clean Learning:
learner f F
In poisoned learning, given a classification problem (X, Y, Ω2 P,F),, a learner f F, training size N and transform T Ω28 - 12 the learner has access to a poisoned training set obtained by applying T to the clean training set and thus the resulting classifier can be denoted as fT(Dx) where Dy P.N. The symmetric distance between the clean training set and the poisoned training set, i.e. [T(DN) Dxl (DT(D)) \ DN) U (DN T(Dx) )),, is called the attack size, which corresponds to the minimum total number of insertions and removals needed to change one training set to the other.
Poisoned Learning:
Total Variation Distance: The total variation distance between two distributions U and over the sample space Ω is 5(U, V) maxaço (U) V(4),, which denotes the largest difference of probabilities on the same event for U and V.
Lethal Dose Conjecture
4.1 The Conjecture
Below we present a more formal statement of Lethal Dose Conjecture:
Lethal Dose Conjecture
For a classification problem (X, Y, P,F), let zo E X be an input and yo = arg max, P(y)ar) be the maximum likelihood prediction.
Let be the smallest training set size such that there exists learner E F with
Prifp., (xo) = yo] 2 т for some constant
For any given training set size and any learner / E F, there a mapping : R - 9 with Pr(ST(p.) = yo] < 1/|Y| while [D( - Dx S ((1nn) N.
3

---

Informally, if the most data-efficien learner takes at least n clean samples for an accurate prediction, then when a potentially poisoned, size-N training set is given, any defense can tolerate at most (N//n) poisoned samples while ensuring accuracy.
Intuitively, if one needs samples to have a basic understanding of the task, then when ((N/n) samples are poisoned in a size-N training set, sampling n training samples will in expectation contain some poisoned samples, preventing one from learning the true distribution. Theoretically, the conjecture offers an intuitive way to think about or estimate the upper bound for robustness for given task: To find out how many poisoned samples are tolerable, one now considers data efficiency instead. Practical implications are included in Section 7
Notably, this conjecture characterizes the vulnerability to poisoning attacks of every single test sample To rather than a distribution of test samples. While the latter type (i.e. distributional argument) is more common, pointwise formulation is in fact more desirable and more powerful.
Firstly, pointwise argument can be easily converted into a distributional one, but the reverse is difficult. Given distribution of zo and the (pointwise) 'lethal dose' for each 2o. one can define the distribution of the 'lethal dose' and its statistics as the distributional 'lethal dose". However, it is hard to uncover the 'lethal dose" for each 2g from distributional arguments.
Secondly, samples are not equally difficult in most if not all applications of machine learning: To achieve the same level of accuracy on different test samples, the number of training samples required can also be very different. For example, on MNIST, which is task to recognize handwritten digits, samples of digits '1' are usually easier for models to learn and predict accurately, while those of digits '6', '8' and '9 are harder as they can look more alike. In consequence, we do not expect them to be equally vulnerable to data poisoning attacks. Compared to a distributional one, the pointwise argument better incorporates such observations.
4.2 Proving The Conjecture in Examples
In this section we present two examples of classification problems, where we can precisely prove Lethal Dose Conjecture. For coherence, defer the proofs to Appendix A B C and D
4.2.1 Bijection Uncovering
Definition (Bijection Uncovering). For any k, Bijection Uncovering is a k-way classification task (X, Y, N, defined as follows:
The input space X and the label set Y are both fiite sets of size ls (i.e. |X| | k):
The true distribution P corresponds learners), and Vx E XX Vy E Y, P(x, y) = I[g(z) =
bijection g from X Y (note that g is unknown to
For y. o E Y, let Teeeg" :22h + Ω be a transform that exchanges all labels y and yf in a the given training set (i.e. a sample is originally labeled y, its new label will become y' and vice versa). The set of plausible learners F contains all learners I such that Pr(fn((o) = y)
Pr(fT,..((D)aa = for all y, s/ E Y and D E E..
This is the setting where there is one-to-one correspondence between inputs and classes. This is considered the 'easiest' classification as describes the case of solving k-way classification given pre-trained, perfect feature extractor that puts samples from the same class close to each others and samples from different classes away from each others. In this case, since one knows whether two samples belong to the same class not, samples can be divided into k clusters and the task is essentially uncovering the bijection between clusters and class labels.
Intuitions for The Set of Plausible Learners F. The set of plausible learners F is a task deeendenn set and we introduce it to make sure that the learner indeed depends on and learns from training data. Here we explain in detail the set F in definition 1: The set of plausible learners F contains all learners f such that (ra) = y] = Pr(fT,,.(())(rr (#o) = y'] for all y. Intuitively, says that if one rearranges the labels in the training set, the output distribution will change accordingly. For example, say originally we define class 0 to be cat, and class 1 to be dog, and all dogs in the training set are labeled O and cats are labeled In this case, for some cat image Fo. a learner f predicts O with probability of 70% and predicts 1 with probability of 30% What
and D E S2

---

happens if we instead define class to be cat, and class 0 to be dog? Dogs in the training set will be labeled 1 and cats will be labeled 0 (i.e. label 0 and label in the training set will be swapped). If is a plausible learner, meaning that it learns the association between inputs and outputs from the dataset, we expect the output distribution to change accordingly, i.e. now f will predict 1 with a probability of 70% and predict O with a probability of 30%. Consequently, an example of a learner that is not plausible is as follow: A learner that always predicts O regardless of the training set, regardless of whether we associate O with dog with cat.
Lemma 1 (Clean Learning of Bijection Uncovering). In Bijection Uncovering, given constant E (1/2, 1), for any input Zo E X and the corresponding maximum likelihood prediction yo = arg max, Po)) let n be the smallest training set size such that there exists a learner F with Pr[SD, (zo) = yo] 2 Then n 2 ((k), i.e. the most data-efficien learner takes at least Okk)
clean samples s for an accurate prediction.
Lemma 2 (Poisoned Learning of Bijection Uncovering). In Bijection Uncovering, for any input To E X and the corresponding maximum likelihood prediction yo arg maxy P(y|zo), for any given training set size N, and any learner f E F, there is a mapping T D - Ω with Pr[fr Pr[fr(Dy)(20) = yol S 1/ while E[[T(DN) - Dxll I @(1/k) -N, i.e. poisoning ((1/k) of the entire training is sufficient break any defense.
for
From Lemma and Lemma 2] we see for Bijection Uncovering, the most data-efficient learner takes at least ((k) clean samples to predict accurately and any defense can tolerate at most ((1/k) of the training set being poisoned. The two quantities are inversely proportional, just as indicated by Lethal Dose Conjecture.
4.2.2 Instance Memorization
Definition 2 (Instance Memorization). For any k and m, Instance Memorization is a k-way classifi- cation task XXYY S,Y,,,,,, F) defined as follows:
The imput space X and the label set are both finite with |X| = - and [Y] = k;
The true distribution P corresponds leurners), and Vo E X, E Y,, P(x,2) v) 11(())=))))))) y)/m;
mapping 9 from X to Y (note that g is unknown to
82 + Ω be transform that exchanges labels y and y for all samples with an input To in given training set (i.e all (Io.z) 8) will become (Io. and vice versa). The set of plausible learners F contains all learners such that PrifD(zo) yl Pr[fT (D) = y') for all y, v.v² E and D E Ω²
For u.v. E Y, let T Tyo
This is the setting where labels for different inputs are independent and learners can only predict through memorization. This is considered the 'hardest' classification problem in sense that the inputs are completely uncorrelated and no information is shared by labels of different inputs.
Lemma 3 (Clean Learning of Instance Memorization). In Instance Memorization, given a constant T E (1/k, 1). for any input xo E X and the corresponding maximum likelihood prediction yo = arg max. ((y)(r)). let n be the smallest training set size such that there exists learner f E F with Pr[fD, (zo) = yol 2 т. Then n Z ((m), i.e. the most data eafa-efficient learner takes at least (mm) clean samples for accurate prediction.
Lemma (Poisoned Learning of Instance Memorization). In Instance Memorization, for any input va E X and the corresponding maximum likelihood prediction yo arg maxy P(y for any given training set size N, and any learner f E F, there is a mapping T 22 + 22 with yo] S 1/|||| while El[T(DN) DNll < @(1/m) N. i.e. poisoning 0(1/m) of the entire training set is sufficient to break any defense.
Pr Pr[fr(D))
From Lemma 3 and Lemma 4 we observe that for Instance Memorization, the most data-efficient learner takes at least (m)) clean samples to predict accurately and any defense can tolerate at most ((1/m) of the training set being poisoned. The two quantities are, again, inversely proportional, which is consistent with Lethal Dose Conjecture. This is likely no coincidence and more supports are presented in the following Sections 5 5land
5

---

An Alternative View from Distribution Discrimination
In this section, we offer an alternative view through the scope of Distribution Discrimination. Intu- itively, if for two plausible distribution U and V over S2 the corresponding optimal predictions on some zy are different (i.e. arg max, Pr[U (y]a)) * arg max, (r]V(y) then learner must (implicitly) discriminate these two distributions in order to predict correctly. With this in mind, we present the following theorems. The proofs are respectively included in Appendix [
Theorem 1. Given two distributions U and V over Q, for any function f 22 -> {0, 1), have
En~ud [J(D)] - En--- [S(D) S n. -0(U.V))
where 8(U, V) is the total variation distance between U and V. Thus for a constant T, ED-U [f(]]]][[]]]]]]]] ED>v=[f(D) 2 implies n 7/8(U, V) (1/S(UU V))
Theorem 2. Given two distributions and V over Q, for any function f f Q2 + {0,1), there is stochastic transform T Q2 + 22,, such that T N) is the same distribution as V (thus ED-UN ([((()) E [f [D)) = 0) and E [T(D) DI| = V) N.
Theorem 1 implies that to discriminate two distributions with certain confidence, the number of clean samples required at least ((1/5(U; V)), which is proportional to the inverse their total variation distance; Theorem suggests that for size-N training set, the adversary distribution indistinguishable given the ability to poison 8(U, V) .N samples in expectation. This is consistent with the scaling rule suggested by the Lethal Dose Conjecture. We will also see in Section 6 how the theorems help the analysis of classification problems.
make the two
6 Verifying Lethal Dose Conjecture in Isotropic Gaussian Classification
In this section, we analyze the case where data from each class follow multivariate Gaussian distribution and we will prove the very same scaling rule stated by Lethal Dose Conjecture.
Definition (Isotropic Gaussian Classification). For any l and d, Isotropic Gaussian Classification is k-way classification task (X, Y, F) defined follows:
The input space X is Rd and the label set Y is a finite set of size k (i.e.lY
-For y E Y, (yy E &d denotes the (unknown) center of class and the true distribution P is:
(VY E) ((y)=k (V EY P(zly) (2m)arIE -1e 1,111111/1 Class y is a Gaussian N(py)
Labels uniformly distributed
(1)
The set of plausible learners F contains all unbiased, non-trivial learners, meaning that for any I E F, given any Io. and any plausible P (i.e. the same form as Equation Tbtt with potemtially different pyy where yo arg maxy P(a/(ao) is unique, have Pr[Jn, (zo) = yoo] and (Vy # yo) Pr(fD, (mo) v) S for all n 2
First we present claim regarding the optimal prediction yo corresponding to given input zo: Claim 1. In Isotropic Gaussian Classification, for any 2p, the corresponding maximum likelihood prediction yo arg max, (yy] ) is arg miny ||20 Myll-
This follows directly from Equation
V/o = arg max, P(y] arg max,, V2x
11
arg min, || Myll. Without loss of generality and with slight abuse of notation, assume in the rest of Scction (6) that μı, #2 are respectively the closest and the second closest class centers to
To and therefore Wo is the optimal prediction. Let d, I. 14 and d2 1| Pal be the distances of μ40 and μr to Zg. An illustration is included in Figure ((a)
First we define parameter A that will later help us to analyze both clean learning and poisoned learning of Isotropic Gaussian Classification: is the total variation distance between two isotropic Gaussian distribution with centers separated by distance of d2 d1, i.e. A 88U, V) for some N(, T) and Ni(,, T) where || p'll = d2 - dr. We introduce lemma proved by Devroye et al. [9)

---

d2
d2
122
H2
142
H1
Xg
X
(a) Clean
(b) Poisoned
Figure 1: Illustrations of Isotropic Gaussian Classification under clean learning and poisoned learning, where [41, A2 are centers for clean training samples with labels I (red) and 2(blue); μz is the center for the poisoned training samples with labels 2 (purple). Note that the illustrations contain only the two closest classes to zo and the setting contains 2 classes.
Lemma 5 (Total variation distance for Gaussians with the same covariance 91). For two Gaus- sian distribution U Nu, Σ) and V N(4', E), their total vuriation distance is 5(U,
(r( [-r, where v(= 11)) (11 x2)/22
= (2/Va) So dt is Thus A = Pr [L, & d2 d = ((d2 - dz)/ where erf((z) the Gaussian error function.
Lemma 6 (Clean Learning of Isotropic Gaussian Classification). In Isotropic Gaussian Classification.
given a constant T E (1/2, 1), (1),,fo for any input To E and the corresponding maximum likelihood prediction yo arg maxy Ply let be the smallest truining set size such that there exists learner I E F with Pr[Jp., (xo) = Vol 2 т. Then n 2 (k) iee. the most data-efficient learner takes at least ((k/A) clean samples for an accurate prediction.
Lemma 7 (Poisoned Learning of Isotropic Gaussian Classification). In Isotropic Gaussian Clas- sification, for any input To E X and the corresponding maximum likelihood prediction yo arg max, P(y ). for any given training set size N, and any learner f E F, there is a mapping : 22 + .2% with Pr(ff(Dx)( = yol S 1 while E[[T(Dx) - Dx s O(A/k) N, i.e.
poisoning O (A/k) of the entire training set is sufficient to break any defense.
The proofs of Lemma 6 and Lemma are included respectively in Appendix G and H Intuitively, what we do is to construct a second, perfectly legit distribution that not far from the original one (measured with the total variation distance), or fail on the one we construct. If it fails on the original one, the adversary achieves its goal even construct, the adversary still succeed
that any classifier must either fail on the original one
without poisoning the training set. If it fails the by poisoning only a limited fraction of the training set because the distribution we construct is close the original one (measured with total variation distance).
Through the lemmas, we show that for Isotropic Gaussian Classification, the most data-efficient learner takes at least (k/ A) clean samples to predict accurately and any defense can be broken by poisoning ((A/k) /k) of the training set, once again matching the statement of Lethal Dose Conjecture.
Practical Implications
7.1 (Asymptotic) Optimality of DPA and Finite Aggregation
In this section, we highlight an important implication of the conjecture: Deep Partition Aggregation 20 and its extension, Finite Aggregation (34) are (asymptotically) optimal- -usng the most data- efficient learner, they construct defenses approaching the upper bound of robustness indicated by Lethal Dose Conjecture within constant factor.
Deep Partition Aggregation 20: DPA predicts through the majority votes of base learners trained from disjoint data. Given the number of partitions & hyperparameter, DPA is a learner constructed
7

---

using a deterministic base learner f and a hash function h : X x Y + [k] mapping labeled samples
integers between 0 and ls 1. The construction is:
DPAD(10) arg max D (zo. y) arg max yEy
(fp) = y
where P. ((,,)) D h(x v) 8) is a partition containing all training samples with hash value of and DPAD y) = Σ [rr (xo) = y) denotes the average votes count for class y- Ties are broken by returning the smaller class index in arg max.
Theorem 3 (Certified Robustness of DPA against Data Poisoning (0 Given a training set and an imput zo. let yo (PAA((2)) then for any training set D' with
k 2
(PPAD(EO v) 1 1 < yol
D D'1 <
DPAAn vo)
max y=yo
k
we have (=0) = DPAD (Ir), meaning the prediction remains unchanged with data poisoning.
Let be the average size of partitions, i.e. n =E |Pl/k= = N/k where N = D is the size of the training set. Assuming the hash function h X Y - [k] uniformly distributes samples into different partitions, we have DPA v) R Pr[Sp,, (xo) y and therefore the right hand side of Equation approximates
PriSD. (5o) = yo] maxy Pr.fD. (xo) = vl N θ N
2n
when the base learner f offers margin A = Pr[jD, (zo) = yol maxy Pr[fp. (xo) 2 T with n samples for some constant т. When f is the most data-efficient learner taking n clean samples with margin A > for input zo, then given a potentially poisoned, size-N training set is given, DPA (using f as the base learner) tolerates θ (N/n) poisoned samples, approaching the upper bound of robustness indicated by Lethal Dose Conjecture within a constant factor.
The analysis for Finite Aggregation (FA) is exactly the same by substituting Theorem with the certified robustness of FA. For details, please refer to Theorem 2 by Wang et al. 34]
7.2 Better Learners to Stronger Defenses
Assuming the conjecture is true, we have in hand the (asymptotically) optimal approaches to convert data-efficient learners to strong defenses against poisoning. This reduces developing stronger defenses finding more data-efficient learners. In this section, as a proof of concept, show that simply using different data augmentations can increase the data efficiency of base learners and vastly improve (double even triple) the certified robustness of DPA, essentially highlighting the potential of finding data-efficient learners in defending against data poisoning, which has been a blind spot for our community.
Setup. Following Levine and Feizi 20 we use Network-In-Netwonk 21 architecture for all base learners and evaluate CIFAR- 10 18 and GTSRB 29 For the baseline (DPA, baseline), we follow exactly their augmentations, learning rates (initially 0.1, decayed by factor of 1/5 at 30%, 60%, and 80% of the training process), batch size (128) and total epochs (200). For results (DPA augo and DPA_augl on CIFAR- 10; DPA_aug on GTSRB), we use predefined AutoAugment (6] policies for data augmentations, where DPA_augO uses the policy for CIFAR- 10, DPA_aug uses the policy for Imagenet and DPA_aug learning rate of 0.005, batch size of 16 for 600 epochs on CIFAR-10 10 and 1000 epochs on GTSRB.
l_aug uses the policy for SVHN, all included in torchvision 24] We use an initial
Evaluation. First, we evaluate the test accuracy of base Iearners with limited data (i.c. using 1/k of the entire training set of CIFAR-10 and GTSRB where k ranges from 50 to 500). In Figure 2(a) simply using AutoAugment greatly improves the accuracy of base learners with limited data: On CIFAR-10. 10, with both augmentation policies, the augmented learners achieve similar accuracy the baseline using only 1/2 of data (i.e. with & that is twice as large); On GTSRB, the augmented learner achieves similar accuracy the baseline using only 1/4- 1/3 of data.
Now we use more data-efficient learners DPA to construct stronger defenses. For baselines, we use DPA with h 50, 100, 250 on CIFAR-10 10 and k 50, 100 GTSRB, defining essentially 5
8

---

OFFAR-10haseliiv
Certifled Accuracy
DRA, Sai
DM augo0k--000
Certified Accuracy
DOA baselliee---1000 DeA, (ugbkk200000
Accuracy
beseli
CIAFR-
DM 1i__ 100)
mx
oog_ougt(K0200
12%
GTSRB
?
Number of Partition
Attack Size
Attack Size
(a) Test accuracy learners using
(b) CIFAR-10 (setting 1)
(c) CIFAR-10 (setting 2)
1 /k of the entire training set
Certified Accuracy
DRA besciine(k-255)
Sug0(k-500)
Certified Accuracy
DPA, 50)) DPA 15A_au
Certified Accuracy
60%
GWW.bapelinee--. DPA (MM,k00)/=4000
DFA (k00
50%
40%
40%
92%
20%
20%
20%
30
50
100 125
150
175 200
Attack Size
Attack Size
Attack Size
(d) CIFAR-10 (setting
(e) GTSRB (setting
(1) GTSRB (setting 2)
Figure 2: Experiments that construct stronger defenses against data poisoning by using more data- efficient base learners for DPA. By simply using different data augmentations to improve the data efficiency of base learners, the certified robustness can be respectively doubled and tripled CIFAR-10 10 and GTSRB without sacrificing accuracy.
Cortitel Accuney (CA()
Bagging
Certified Accuracy
3000 2-
0.8
3000 r=21
DPA
20000, r=20
0.6-
KNN
k- k-00000, r=21
0.4
INN
0.2
200
U00
0000
800
1000
Poisoning Sizee
Attack Size
(a) The evaluation conducted by Jia et al. [6] DPA using neural networks as hase learners outperformed by nearest neighbors.
(b) Our evaluation of DPA: By using ra- dius nearest neighbors as hase learners, DPA achieves similar level of robustness near- est neighbors defenses [6
Figure 3: Comparing the certified robustness of DPA with the nearest neighbor defenses [6] on CIFAR-10. suggesting kNN and rNN are no stronger defense than DPA but are using more data- efficient learner given the accuracy requirements.
settings. When using augmented learners in DPA, we increase k accordingly so that the accuracy of
base learners remains at the same level as the baselines, as indicated by Figure 2(a) On CIFAR-10 in
Figure 2(b 2 and [(d) the attack size tolerated by DPA is roughly doubled using both augmented learners for similar certified accuracy. On GTSRB, in Figure 2 and 2( the attack size tolerated
by DPA is more than tripled using the augmented learner for similar certified accuracy.
The improvements are quite significant, corroborating the potential of this practical approach developing stronger defenses against poisoning through finding more data-efficient learners.
7.3 Better Learners from Stronger Defenses
Assuming the conjecture is true, when some defense against data poisoning is clearly more robust than DPA (even in restricted cases), there should be more data-cfficient learner. Jia et al. [16]

---

propose to use nearest neighbors, i.e. KNN and rNN, to certifiably defend against data poisoning. Interestingly, in their evaluations, kNN and rNN tolerate much more poisoned samples than DPA when the required clean accuracy is low, as shown in Figure 3(a) Here we showcase how a learner is derived from their defense, which, when being used as hase learners, boosts the certified robustness of DPA to a similar level to the nearest neighbors defenses.
In [6]. histogram of oriented gradients (HOG) 7 used as the predefined feature space to estimate the distance between samples. Consequently, we use radius nearest neighbors over HOG features as the base learner of DPA. Given a threshold r, radius nearest neighbors find the majority votes of training samples within an & distance of r" to the test sample. When there is no training sample with distance of we let the base learner output token 1 denoting outliers so that it will not affect the aggregation. The results are included in Figure 3(b) where DPA offers similar robustness curves as KNN and rNN in Figure M(a) by using the aforementioned base learner and hence the same prior.
8 Conclusion
In this work, we propose Lethal Dose Conjecture, which characterizes the largest amount of poisoned samples any defense can tolerate for specific task. We prove the conjecture for multiple cases and offer general theoretical insights through distribution discrimination. The conjecture implies the (asymptotic) optimality of DPA 20 and FA
34 in a sense that they can transfer the most data-efficient learners to one of the most robust defenses, revealing a practical approach to obtaining stronger defenses via improving data efficiency of (non-robust) learners. Empirically, as proof of concepts, we show that simply using different data augmentations can increase the data efficiency base learners, and therefore respectively double and triple the certified robustness of DPA on CIFAR-10 10 and GTSRB. This highlights both the importance of Lethal Dose Conjecture and the potential of the practical approach in searching for stronger defenses.
Acknowledgements
This project was supported in part by NSF CAREER AWARD 1942230, a grant from NIST 60NANB20D134, HR0011 19S0026 (GARD), ONR YIP award N00014-22-1-2211, Army Grant No. W911NF2120076 and the NSF award CCF2212458.
References
[1] Hojjat Aghakhani, Dongyu Meng, Yu-Xiang Wang, Christopher Kruegel, and Giovanni Vi- gna. Bullseye polytope: A scalable clean-label poisoning attack with improved transferabil- ity. In IEEE European Symposium on Security and Privacy, EuroS&P 2021, Vienna, Austria, September 6- 10, 2021, pages 178. IEEE, 2021. doi: 10. 1099/EuroSP51992222211 2000000 URL http:: org/ 10. 1109 0ttp///urSSP119995 1992. 2021.00022
[2] Pranjal Awasthi, Maria-Florina Balcan, and Philip M. Long- The power of localization for efficiently learning linear separators with noise. J. ACM, 636))500 2017. doi: 10. 145/ 3006384. URL https: org 10. 1145/3006384
[3] Maria-Florina Balcan, Avrim Blum, Steve Hanneke, and Dravyansh Sharma. Robustly-reliable learners under poisoning attacks. In Po-Ling Loh and Maxim Raginsky, editors, Conference on Learning Theory, 2-5 July 2022, London, UK, volume 178 of Proceedings of Machine Learning Research, pages 4498 4534. PMLR, 2022. httk::tttt://proeeeet
mlr S.t..prress/v1//
bal cat.annnnaaallll
[4] Ruoxin Chen, Jie Li, Chentao Wu, Bin Sheng, and Ping Li. A framework of randomized selection based certified defenses against data poisoning attacks. CoRR, abs/2009.08739, 2020. URL httpss//:/// org/ abs////sb//00/// 007399
[5] Xinyun Chen, Chang Liu, Bo Li, Kimberly Lu, and Dawn Song. Targeted backdoor attacks on deep learning systems using data poisoning. CoRR, abs/1712 2017. URL. http:
//arxiv. erg/abs/ abs/1712 05526
10

---

[6] Ekin D. Cubuk, Barret Zoph. Dandelion Mané, Vijay Vasudevan, and Quoe V. Le. Au- toaugment: Learning augmentation strategies from data. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019, pages 113-123. Computer Vision Foundation IEFE, 2019. doi: 10. 10..10//CPP.20110 NPTPPR.011.00021 URI.
htttp://openaccess.. thecvf com httppacccsssseeeff..c.o/ottttttr Setpeeeet__ttt___eee_eee 2019/tttl /ubbk hwwprauuuAutttuueeeeeeee html
Learning_ htw.aaag...gggaaaooooorrrrteeeee
[7] Navneet Dalal and Bill Triggs. Histograms of oriented gradients for human detection. In 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2005), 20-26 June 2005, San Diego, CA, USA, pages 886-893, IEEE Computer Society, 2005,
doi: 10.1 2..100/C....200..17..
httpss//://doi org/ 10. 100910..11111011 11091119/VVPPP 2005. 177
[8] Jacob Devlin, Ming-Wai Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume (Long and Short Papers), pages 4171-4186 2019. URL httpp:://w// aclweb org/ http//ntholggyy/// N11//1199111111 1423/
pre-training
[9] Lue Devroye, Abbas Mehrabian, and Tommy Reddad. The total variation distance between high-dimensional gaussians. arXiv preprint Xiv: 1eXiv:1810.00 1810.06693 2018.
[10] Ilaas Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Jacob Steinhardt, and Alistair Stewart. Sever: A robust meta-algorithm for stochastic optimization. In Kamalika Chaud- huri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, vol- ume 97 of Proceedings of Machine Learning Research, pages 1596-1606. PMLR, 2019. URL http:///proceedings mlr. press/ v dwa.onikollllcoooo kosiil9e html
[11] Ji Gao, Amin Karbasi, and Mohammad Mahmoody. Learning and certification under instance- targeted poisoning. In Cassio P. de Campos, Marloes H. Maathuis, and Erik Quaeghebeur, editors, Proceedings of the Thirty- Seventh Conference on Uncertainty in Artificial Intelligence, UAI 2021, Virtual Event, 27-30 July 2021, volume 161 of Proceedings of Machine Learning Research, pages 2135-2145. AUAI Press, 2021. URL 1.61/gao21b html
mlr press/
[12] Jonas Geiping, Liam H. Fowl, W. Ronny Huang, Wojciech Czaja, Gavin Taylor, Michael Moeller, and Tom Goldstein. Witches' brew: Industrial scale data poisoning via gradient matching. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL. https::/ net/ Forum?id=01olnfLLI.
[13] Micah Goldblum, Dimitris Tsipras, Chulin Xie, Xinyun Chen, Avi Schwarzschild, Dawn Song, Aleksander Madry, Bo Li, and Tom Goldstein. Dataset security for machine learning: Data poisoning, backdoor attacks, and defenses. CoRR, abs/2012.10544, 2020. URL |htpps
//arxiv.
10544
[14] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition. pages 770-778, 2016.
[15] Sanghyun Hong. Varun Chandrasekaran, Yigitcan Kaya, Tudor Dumitras, and Nicolas Paper- not. On the effectiveness of mitigating data poisoning attacks with gradient shaping. CoRR, abs/2002. 1497, 2020. URL, httpp::///xxxv.rrrg//
11497
[16] Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong. Certified robustness of nearest neighbors against data poisoning attacks. CoRR, abs/2012.03765. 2020. URL https:///axxi: org/ abs. 03765.
[17] Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong. Intrinsic certified robustness of bagging against data poisoning attacks. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Thin Conference Innovative Applications of Artificial Intelligence.
11

---

IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence,
EAAI 2021. Virtual Event, February 2-9, 2021, pages 7961-7969. AAAI Press, 2021. URL https://ojs. aaai.... org/index..re.ooooooooooooooeer. /ttp//A///articeeeeee/////////
[18] Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
[19] David Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017.
[20] Alexander Levine and Soheil Feizi. Deep partition aggregation: Provable defenses against general poisoning attacks. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.nee 2021.
[21] Min Lin, Qiang Chen, and Shuicheng Yan. Network in network. In Yoshua Bengio and Yann LeCun, editors, 2nd International Conference on Learning Representations, ICLR 2014. Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014. URL http:
//arxiv. prg/abs//311/ 4400
[22] Yuzhe Ma, Xiaojin Zhu, and Justin Hsu. Data poisoning against interrentiallypprivvae learners: Attacks and defenses. In Sarit Kraus, editor, Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019. pages 4732 4738. ijcai.org, 2019. doi: 10.24963/ijcai. 2019/657. 24963/ijcai 2019/657
/ttp:////.....111555777 URL httph:t////oii org/10
[23] Saeed Mahloujifar, Dimitrios I. Diochnos, and Mohammad Mahmoody. The curse of concentra- tion in robust learning: Evasion and poisoning attacks from concentration of measure. CoRR. abs/1 NA/18809000633.. 2018.
org/
03063
[24] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf. Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024-8035. Curran Associates, Inc., 2019. http:
www.errpp.cccpppeeeee pytochhtorch--o an- Srrperaiiire-stteeeeeig--rrrrrrr httpahhhgeppppooroaaaeeeeeeeeeea 1ibrary pdf
[25] Andrea Paudice, Luis MonzzzzG András György, and Emil Lupu. Detection of adver- sarial training examples in poisoning attacks through anomaly detection. CoRR, abs/1 htbs//802.0304,,
2018. URLhhttp: httt:://arxxiii /awpxv..ivvv/////////aa//aaaav . org/ abs/ http//882..0000 03041
[26] Elan Rosenfeld, Ezra Winston, Pradeep Ravikumar, and J. Zico Kolter. Certified robustness to label-fiipping attacks via randomized smoothing. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 8230-8241. PMLR, 2020. http //proceedings.nut mlr wwtppp/reeeereeeeeeeee add0oo html
[27] Aniruddha Saha, Akshayvarun Subramanya, and Hamed Pirsiavash. Hidden trigger backdoor attacks. In The Chirty-Fourthy AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pages 11957-11965. AAAI Press, 2020. URL https //aaai. org/ metaai/org/o///innieeeee wjs/index.... Ctap/AAAI/AA attpaarriieeeeeeeeeeeeeeeeeeeeee
[28] Ali Shafahi, W. Ronny Huang, Mahyar Najibi, Octavian Suciu, Christoph Studer, Tudor Dumi- tras, and Tom Goldstein. Poison frogs! targeted clean-label poisoning attacks on neural networks. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Biancha and Roman Garnett, editors, Advances Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8. 2018, Montréal, Canada, pages 6 6106-6116, 2018. URL / ptt.: neurips http:/hhhhhhaa http:p//0....haa2222222222222230 htte110000000011111----eeeeee... Abstract.html
12

---

[29] Johannes Stallkamp, Mare Schlipsing, Jan Salmen, and Christian Igel. Man vs. computer: Benchmarking machine learning algorithms for traffic sign recognition. Neural Networks, 32: 323-332, 2012. doi: 10. 10.00/..neune..2122222000 neunet 02106
URL httph:ttt/:/ttt org/ 1016/]
[30] Jacob Steinhardt, Pang Wei Koh, and Perey Liang. Certified defenses for data poison- ing attacks. Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wal- lach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017. December 4-9. 2017. Long Beach, CA. USA. pages 3517-3529, 2017. URL https://proceeddnggs iereeedddnnnn.euuippioeee neurips https/cpppppp/////////////
Bar311ba459f9e4440 147310beesr9946ool66666662/a2al 451114452555511111444 Aws.dddtt---rttttthhhh..h.
[31] Brandon Tran, Jerry Li, and Aleksander Madry. Spectral signatures in backdoor attacks. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018. NeurIPS 2018. December 3-8, 2018, Montréal, Canada, pages 8011-8021, 2018 URL ptpp://////o http://///pooooednnnnnnniiiipppp neurips hhaaper/2118/aahh/// http:///200222220004/402/2222220 http://t.....ttttt.........
[32] Alexander Turner, Dimitris Tsipras, and Alcksander Madry. Label-consistent backdoor attacks.
CoRR. abs/ http/1912..02777 2019. URL http://t://aaii org/ ///////////// 1912.02771
[33] Bolun Wang. Yuanshun Yao, Shawn Shan, Huiying Li, Bimal Viswanath, Haitao Zheng, and Ben Y. Zhao Neural cleanse: Identifying and mitigating backdoor attacks in neural networks. In 2019 IEEE Symposium on Security and Privacy, SP 2019, San Francisco, CA. USA, May 19-23, 2019, pages 707-723 IEEE, 2019. doi: 10.1109/5P2219.00003... URL attps://doo http::///doo.or/1/../.1 1109/SP SP, 00031
[34] Wenxiao Wang, Alexander Levine, and Soheil Feizi. Improved certified defenses against data poisoning with (deterministic) finite aggregation. CoRR, htts/2222.02628, 2022.
[35] Maurice Weher, Xiaojun Xu, Bojan Karlas, Ce Zhang, and Bo Li. RAB: provable robustness against backdoor attacks. CoRR, abs/2003.08904, 2020. URL https: http://aavvvvr//eeee /bbs// 2003.08904
[36] Wayne Xiong, Jasha Droppo, Xuedong Huang, Frank Seide, Mike Seltzer, Andreas Stolcke, Dong Yu, and Geoffrey Zweig, Achieving human parity in conversational speech recognition. CoRR, abs/1610.05256, 2016. URL/http://are //atti: orgooogggaao. abs///1b/111...../ 05256
[37] Chen Zhu, W. Ronny Huang, Hengduo Li, Gavin Taylor, Christoph Studer, and Tom Gold- stein. Transferable clean-label poisoning attacks on deep neural nets. In Kamalika Chaud- huri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, vol- ume 97 of Proceedings of Machine Learning Research, pages 7614-7623. PMLR, 2019. URL http://proceeedings mlr, wwwpp/pwwsssseeee httpv/99//zzhui/ html
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] In Section] I
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
13

---

(b) Did you include complete proofs of all theoretical results? included Appendix.
[Yes] Some proofs are
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [Yes]
(b) Did you mention the license of the assets? [No]
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're
using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [No] Both CIFAR-I0 and GTSRB are standard benchmarks.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "Xwm2zsO3QNj", "reviewer": "Reviewer_a652", "summary": "The paper suggests a conjecture that quantifies what is the maximal fraction of training data that might be poisoned, while achieving a given required accuracy rate $\\epsilon$. Specifically, the conjecture is that roughly $1/n$ of the training data is the maximal poisoned data fraction, where $n$ is the sample complexity of the task, that is, the sample size required to achieve accuracy $\\epsilon$ in a \"clean\" environment (without presence of an adversary). The conjecture is proved for some special cases such as instance memorization. Another theoretical aspect of the paper is a general view of the poisoning problem through distribution discrimination. Practically, the paper summarizes results of some experiments supporting the conjecture: On one hand, robust learners can be derived from data-efficient learners, and on the other hand, data-efficient learners can be derived from robust learners.", "questions": "1. In the definition of a learner, and poisoned learning: The domain of $T$ and $f$ seems to be defined as infinite vectors where I guess it should be finite vectors?\n2. The formulation of the formal statement of the conjecture in page 3 is not justified enough, in my opinion. It seems that the conjecture is formulated with respect to a specific given data point $x_0$. I guess that this what a \"specific task\" (as written in the introduction) means? However, a \"specific task\" might be understood as drawing the test point from a *specific* hidden marginal distribution over instances, as usually done in PAC learning. Also, isn't this suggested formulation might be better? For example, think of a point that can only suffer attacks of a very small size, but on the other hand is not likely to be drawn as a test point. Isn't it better to define the lethal dose to be higher, than what reflects in the conjecture, in this case? (because a wrong prediction on this point is not lethal).\n3. In definition 1: What does \"plausible learners\" mean? In what sense are they plausible?\n4. The paragraph that comes after definition 1 is not clear to me. What are the \"classes\" here? In what sense is this setting the easiest?\n5. Isn't the proof of Lemma 1 is just by the fact that the VC-dimension of the corresponding hypothesis class is $k$? Just think of the $k$ labels as all possible binary labelings of $\\log_2(k)$ data points.\n6. The paragraph that comes after definition 2 is not clear to me. Why is this setting so much harder compared with the setting of definition 1? Also, definition 2 seems like a generalization of definition 1, and if that is indeed the case,  perhaps it is good to mention that.", "limitations": "Yes, except for what is written in question 2 about the formulation of the conjecture.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The conjecture sounds reasonable. The informal arguments as well as the experiments supporting it are quite convincing.\n2. The \"distribution discrimination\" view of the problem is intuitive and insightful.\n3. The practical technique of using data augmentation to increase accuracy is interesting and insightful.\n4. The idea of deriving data efficient-learners from robust learners is interesting as well.\n\nWeaknesses:\n1. The absence of some standard notions in machine learning that seems related to the paper makes the paper and its contribution harder to understand.  For example, it seems that the terms \"sample complexity\" and \"realizability\" should have been integrated in the basic definitions. Another example is Lemma 1 which seemingly can be simply proved using the well known VC-dimension, which is not mentioned anywhere in the paper (elaboration in  question 5).\n2. The theoretical contribution of the paper is not clear enough to me: The formal statement of the conjecture is not justified enough in my opinion (elaboration in question 2). It is also not explained why the special cases described in Section 4 are interesting, and in what sense they are \"easy\" or \"hard\", as written in the paper (see elaboration in questions 4,6). \n3. There are some unclear parts in the text, which also makes it hard to evaluate the paper's contribution. Examples can be found in questions 1,3. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IpfL2hJEPE7", "reviewer": "Reviewer_7KLu", "summary": "This paper suggests a hypothesis for the necessary and sufficient amount of malicious samples needed asymptotically for successful data poisoning. Most notably, the amount is inversely proportional to the minimum amount of data needed to learn the concept for the chose model class. The hypothesis is proven on some learning scenarios. Empirically, it is shown that learning pipelines using more data efficient base learner can achieve higher certified robustness against poisoning.", "questions": "I have two main questions.\n\n1. How should we interpret $n$ --- the minimum amount of data required by the most sample efficient learner? Given a distribution and a model class for the base learner, $n$ would become a constant, wouldn't it? For example, for a linear separable data distribution with margin $\\epsilon$, $n$ would just be a constant for a given $\\epsilon$. Now, notice the bound is asymptotic, a constant $n$ means the data poisoner always need to poison a constant fraction of the data set. Could you give an example that 1) the model class has a variable $k$, e.g. size of neurons in an NN, 2) $n$ scales with $k$, and 3) the amount of poisoning examples needed has lower order than constant portion given increasing $k$? \n\n2. Correct me if I'm wrong: the hypothesis suggests that a more complex base learner may be more prone to data poisoning attack. On the other hand, a more complexity model (e.g. deep learning models) has the potential to fit both the poisoning data and the clean data separately, while a simple model (e.g. linear classifier) cannot. How do these two view reconcile with each other? This is out of the scope of the paper, and will not be the ground of my acceptance/rejection. But I'm curious about your opinion. Thanks. ", "limitations": "The limitations have been adequately addressed.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper proposes a wholistic idea with ample theoretical and empirical evidence. The message is clear and thought-provoking. I learned something new. Thank you.\n\nIn terms of clarity, this paper is of high quality. The main concepts are mostly clear stated, and the theoretical insights is coupled with intuitive explanation, making it easy to understand by audience with different levels of theoretical background. \n\nFor significance, although the paper is only a hypothesis, the hypothesis statement is thought provoking. The implication to real-world scenario is also impactful: data efficient base learner can achieve higher robustness against poisoning. The empirical evidence further increases the significance.\n\nFor originality, the paper stems from previous work of DPA and FA, the angle is new. Whether the hypothesis is eventually proven true or false, the idea is worth presenting to the machine learning community.\n\nOverall, this paper is of high quality. However, I do have a few lingering problem about the strength of the statement, and hope the authors can clarify.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "AXwHg8sPbPX", "reviewer": "Reviewer_PsFt", "summary": "This paper introduces the Lethal Dose Conjecture (LDC) which speculates on the\nminimum amount of bad or poisoned data samples that a learning algorithm can\ntolerate (or an attacker can manipulate) before its ability to predict breaks\ndown. They conjecture that this number is bounded by Θ(N / n) (using \"Big\nTheta\" asymptotic notation) for datasets of size N and problems where a minimum\nof n correctly labeled examples are needed. They seek to prove this in three\nrestricted settings and provide evidence suggesting it may be true in general.\n\nThey relate this conjecture to two previously published ensembling techniques\n(DFA and FA) that provide robustness when learning on a \"poisoned\" dataset.\nThey show that if LDC is true, then DFA and FA are the best mitigations against\npoisoned data in the limit as the dataset size grows.\n\nA recurring theme is that data efficiency (the ability to fit a pattern with\nfewer examples) is linked to how well a learning algorithm can withstand\npoisoning. Experiments use data augmentation to increase the data efficiency of\nnetwork-in-network learners on CIFAR-10 and GTSRB.\n", "questions": "Please list up and carefully describe any questions and suggestions for the\nauthors. Think of the things where a response from the author can change your\nopinion, clarify a confusion or address a limitation. This can be very\nimportant for a productive rebuttal and discussion phase with the authors.\n\nThere are several nitpicks and typos.\n\nLine 33: I find the \"by doing nothing\" somewhat unclear.\n\nThe use of the term \"certified robustness\" is used several times, but isn't\ndefined. Adding that definition in the introduction would be helpful. It looks\nlike line 79 and 80 are getting at the definition, but I think it would be best\nto make the term crystal clear.\n\nI'm fairly sure the term \"asymptotically\" refers to the growth of the dataset,\nbut that should be stated.\n\nIn Figure 1, you forgot a `\\` in front of `mu_1`.\n\nIn Section 6, (and in the abstract) the upfront claim is that you are verifying\nthe conjecture in \"Gaussian Classification\", but upon further reading it is \nmore restrictive than that. The Gaussian's have equal co-variance and it seems\nthat the learning is happening in a balanced setting where each class has\nroughly the same number of examples. It isn't clear if the result holds beyond\nthis case, but the proof seems to specifically address this case. I think this\n\"balanced equal co-variance\" or some other wording to that effect is needed when \nintroducing this claim (at least in the list of contributions and in the title\nof section 6 or the first sentence).\n\nThis also raises the question: What happens in an unbalanced setting? How does\nthat relate to `n` the minimum number of clean examples needed? When discussing\nthe number `n` there seems to be a presumption that the minimum number of\nexamples. I'm not sure if this is worth stating in the paper or not.\n\nIn the appendix, I did my best to verify the proofs. Nothing stood out as\nobviously wrong, but there were places that I think could benefit from further\nexplanation (at least for me, perhaps its clear to others).\n\nAfter line 5, (lets label them 5.1 - 5.5) I don't see how to get from 5.1 to\n5.2.\n\nOn line 8, it would be more formally correct to say ∈ Θ(k) as Θ represents a\nset of functions of which log(2 - 2τ)/log(1 - 2/k) is a member.  This comment\napplies elsewhere. This is minor as the intention should be generally\nunderstood, but I wanted to point that out.\n\nOn line 19, it wasn't clear to me why `E[| T(D_N) - D_N |] = 2N / k`.\n\nI also marked that I didn't understand steps 46.2 and 46.3.\n\nIt may be of some value to put some of these proofs or parts of these proofs\ninto a proof validator and provide that encoding to provide readers like myself\nwith marginal theoretical ability to feel more confident about their\ncorrectness.  You could codify difficult to encode arguments as assumptions,\nwhich would mean only the truth of the important concepts would need to be\nverified.\n\nI was unable to follow lemma 6 and 7. They would benefit from more explanation.\nWhat is the intuition for taking ε -> 0?\n\n", "limitations": "The authors do not discuss the potential negative impact of this work, but I\nthink this potential is fringe. In some sense the conjecture could give a\nmalicious actor a hint on the amount of work they need to do, but it also lets\nothers know what they need to guard against. I don't think there is any\nimmediate or zero-day exploit that this enables, so in general I think making\npractitioners aware of this (potential) Θ(N / n) relationship is a net social\ngood.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Please provide a thorough assessment of the strengths and weaknesses of the\npaper, touching on each of the following dimensions: originality, quality,\nclarity and significance. You can incorporate Markdown and Latex into your\nreview. See /faq.\n\nThe paper is generally well written, well motivated, and provides a good amount\nof evidence in support of the claim.\n\nI'm not deeply involved in the related literature on data poisoning, so I can't\ncomment on how original the work is, but it seems to be a logical (but\nnon-trivial) next direction given the previous works cited in section 1 and 2.\n\nApart from having a well-chosen name, the actual conjecture provides a useful\nconceptual framework for practitioners to think about data poisoning (or as a\nlimiting case relating to learning on dirty datasets in general). The N/n\nfigure makes intuitive sense but nailing it down to exactly that case is\ntheoretically import.\n\nThe code to reproduce the experiments is provided.\n\nI think the biggest weakness is the choice of datasets and experiments.  I\nthink what is presented is sufficient given the quality of the theoretical\nanalysis, but I would have liked to see the claim tested against a large\n(image-net sized) dataset with a large model, even if the result is: it doesn't\nfollow the theoretically predicted trend, but that could just be suggesting we\nhaven't found efficient enough learners.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-6u3ZObdlBk", "reviewer": "Reviewer_2ZuC", "summary": "This work proposes the *Lethal Dose Conjecture* regarding learnability under training-set attacks -- in particular on the amount of data needed by an attacked (sub)model.  The authors demonstrate their conjecture on simple model classes (e.g., instance based-learners).  They also discuss approaches to approve the performance of existing certified defenses generally.", "questions": "In Sec. 7.2, the argument is made that since DPA is asymptotically optimal, then improving robustness \"reduces developing stronger defenses to finding more data-efficient learners.\"\n* I understand the origin of this claim, but it seems overbroad.  Could it not also be argued that a better/alternative approach is better ways to determine $\\ell_0$ robustness of the individual models beyond the assumption that a single insertion/deletion can arbitrarily change the prediction?\n* Under your claim the number of models may need to grow to $n$ which affects inference time efficiency. If there was some way -- say even an oracle -- to quantify the intrinsic robustness of each submodel, would that not be similarly as good?  If not why? \n\nAssuming the conjecture is true, in what case should an ensemble-based method like DPA be used?  For simplicity of discussion, consider DPA (not FA) with disjoint partitions.\n* By partitioning the training set, an attacker with perfect knowledge can ignore $\\frac{k}{2}$ of the submodels or in other words about $\\frac{1}{2}$ of the training data.  If only $n$ instances are needed to learn the distribution, does this not reduce the best case bound by (about) half specifically if we can certify the robustness of an individual submodel above 1 (as possible with KNN)?\n     * In other words, is partitioning merely a way to dilute the effect of \"overwhelmingly lethal\" instances?\n     * I think this distinction and discussion is more and to some degree glossed over in Section 7.\n* Granted the claim in your paper is that they are only optimal up to a constant factor and what I describe is a (constant) factor of 2.\n* I think clarity on this point is particularly important for me and would improve the paper.\n\nHow do your \"baseline\" experimental results correspond to the published [DPA implementation](https://github.com/alevine0/DPA)?  Does it take out the data augmentation already in the implementation and compare against that?  ", "limitations": "I believe the finding about data efficiency affecting DPA/FA's performance is an obvious one and already known.  Described very briefly, an ensemble's performance sits on top of the performance of its submodels.  If the submodels are made better, the ensemble will improve.  \n* For example, without the base augmentation already in [DPA's implementation](https://github.com/alevine0/DPA/blob/ce25c36721f7529350700b071b9a5e1281c31009/FeatureLearningRotNet/dataloader.py#L97), DPA performs much worse.\n* I am open to be convinced if others think this finding is less obvious.\n\nGao et al. [9] study and provides bounds under instance targeted poisoning attack. The relationship of your work to Gao et al. [9] to your work merits a longer discussion than the partial sentence at the end of Section 2.\n* As more general feedback, I appreciate when in related work the authors include in the text the author(s)'s names with the citation number. I missed that you even noted Gao et al. the first time I read it because it only had the citation number.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Off the top, there are definitely things I like about this paper; at the same time, I have concerns.  My score is currently set to borderline, and the score changed multiple times over the course of thinking about the paper and writing the review. It is my *a priori* expectation this score will change based on discussions with the authors and other reviewers.\n\nThe paper is overall very well-written.  The arguments are laid out clearly.  It uses the right amount of notation to maximize understanding.  Overall, I enjoyed reading it.  I recognize the obvious level of care and thought in the writing.  \n\nI also recognize that there is implicitly some level of courage in writing a conjecture paper and that reviewers should be understanding that even a wrong conjecture can advance science.  Nonetheless, I think the bar for such papers should be quite high, and most conjecture papers may be better suited as a preprint unless especially incisive.  I am not convinced this paper meets that latter bar in particular given related work.\n\nI appreciate the demonstration of the conjecture on simple model classes (e.g., bijective learner, instance-based memorized learner).  There are special properties to those learners that make me concerned of if/how readily the conjecture generalizes.  I understand that the argument is made that the conjecture applies to the two extremes of learnability -- hardest and easiest -- so in theory it applies elsewhere.  I would have hoped had the conjecture been demonstrated on even a simple parametric model class (e.g., a linear model); I also understand that this easier said than achieved.  Overall, I am concerned the claims may be overstated.\n\nI thought the point made in Section 7.3 \"*If assuming the conjecture is true, when some defense against data poisoning is clearly more robust than DPA (even in restricted cases), there should be a more data-efficient learner.*\" was well-stated and effective.  I think the paper would be improved if that point was made more clearly earlier.\n*  As a note, I think there may be a typo at the beginning of that sentence.\n\nI appreciate that the authors consider both DPA and FA.  I think the exposition would be clearer focusing exclusively on DPA and having a statement in the related work about how the arguments made about DPA generalize to FA.  DPA is the older method and the gains from FA are often quite marginal and focused mostly in the tail of the certification bound curve (Wang et al. 2022 Table 1). \n* Granted FA is newer and can lead to improvements at the expense of increased training and inference costs.  I do not think repeatedly mentioning FA here achieves much beyond making FA better known.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept