Deep Partition Aggregation: Provable Defenses against General Poisoning Attacks
Authors: Alexander Levine
Soheil Feizi
Venue: ICLR 2021 Poster (2021)
Keywords: bagging
ensemble
robustness
certificate
poisoning
smoothing

Abstract: Adversarial poisoning attacks distort training data in order to corrupt the test-time behavior of a classifier. A provable defense provides a certificate for each test sample, which is a lower bound on the magnitude of any adversarial distortion of the training set that can corrupt the test sample's classification.
We propose two novel provable defenses against poisoning attacks: (i) Deep Partition Aggregation (DPA), a certified defense against a general poisoning threat model, defined as the insertion or deletion of a bounded number of samples to the training set --- by implication, this threat model also includes arbitrary distortions to a bounded number of images and/or labels; and (ii) Semi-Supervised DPA (SS-DPA), a certified defense against label-flipping poisoning attacks. DPA is an ensemble method where base models are trained on partitions of the training set determined by a hash function. DPA is related to both subset aggregation, a well-studied ensemble method in classical machine learning, as well as to randomized smoothing, a popular provable defense against evasion (inference) attacks. Our defense against label-flipping poison attacks, SS-DPA, uses a semi-supervised learning algorithm as its base classifier model: each base classifier is trained using the entire unlabeled training set in addition to the labels for a partition. SS-DPA significantly outperforms the existing certified defense for label-flipping attacks (Rosenfeld et al., 2020) on both MNIST and CIFAR-10: provably tolerating, for at least half of test images, over 600 label flips (vs. < 200 label flips) on MNIST and over 300 label flips (vs. 175 label flips) on CIFAR-10. Against general poisoning attacks where no prior certified defenses exists, DPA can certify $\geq$ 50% of test images against over 500 poison image insertions on MNIST, and nine insertions on CIFAR-10. These results establish new state-of-the-art provable defenses against general and label-flipping poison attacks. Code is available at https://github.com/alevine0/DPA

Published as a conference paper at ICLR 2021
DEEP PARTITION AGGREGATION: PROVABLE DEFENSES AGAINST GENERAL POISONING ATTACKS
Alexander Levine & Soheil Feizi
Department of Computer Science University of Maryland College Park, MD 20742, USA falevineC, sfeizi @ccs umd.
ABSTRACT
Adversarial poisoning attacks distort training data in order to corrupt the test-time behavior of a classifier. A provable defense provides certificate for each test sample, which a lower bound on the magnitude of any adversarial distortion the training set that corrupt the test sample's classification. We propose novel provable defenses against poisoming attacks: (i) Deep Partition Aggregation (DPA), a certified defense against general poisoning threat model, defined the insertion or deletion of a bounded number of samples to the training set by implication, this threat model also includes arbitrary distortions to a bounded number of images and/or labels; and (ii) Semi-Supervised DPA (SS-DPA), certi- fied defense against fabe-flipping poisoning attacks. DPA an ensemble method where base models are trained on partitions of the training set determined by a hash function. DPA is related to both subset aggregation, a well-studied ensem- ble method in classical machine learning, well to randomized smoothing, popular provable defense against evasion (inference) attacks. Our defense against label-fiippngg poison attacks, SS-DPA, uses sepi-super learning algorithm as its base classifier model: each base classifier is trained using the entire unla- beled training set in addition the labels for partition. SS-DPA significantly outperforms the existing certified defense for label-flipping attacks (Rosenfeld et al., (020) on both MNIST and CIFAR-10: provably tolerating, for least half of test images, over 600 label flips (vs. < 200 label flips) on MNIST and over 300 lahel flips (vs. 175 label flips) on CIFAR-10. Against general poi- soning attacks where no prior certified defenses exists, DPA can certify 2 50% test images against over 500 poison image insertions on MNIST, and nine insertions CIFAR-10. 10. These results establish new state-of-the-art provable defenses against general and label-niipping poison attacks. Code is available at https:://itthue com/ cow.aleevne0//ee....
INTRODUCTION
Adversarial poisoning attacks are an important vulnerability in machine learning systems. In these attacks, an adversary can manipulate the training data of a classifier, in order to change the clas- sifications of specific inputs at test time. Several poisoning threat models have been studied in the literature, including threat models where the adversary may insert new poison samples (Chen et al. 2017). manipulate the training labels (Xiao et al., 2012: Rosenfeld et al. 22220). or manipulate the training sample values (Biggio et al.] 2012; Shafahi et al.) (2018). A certified defense against a poisoning attack provides a certificate for each test sample, which is a guaranteed lower bound on the magnitude of any adversarial distortion of the training set that corrupt the test sample's classification. In this work, we propose certified defenses against two types poisoning attacks:
General poisoning attacks: In this threat model, the attacker number of samples from the training set. In particular, the attack magnitude p is defined as the cardinality of the symmetric difference between the clean and poisoned training sets. This threat
insert remove bounded

---

Published as a conference paper at ICLR 2021
Label
flips (Percent of Training Set
0.0
0.1
02
0.3
0.4
0.5
0.6
0.7
0.8
1.0
0.8
Certified Accuracy
Rosenfeid et al., q 0.05
Rosenfeld et al., 0.025
Rosenfeld q == 0.0125
Our model, 1200
0.4
Our model, k 3000
0.0
100
200
300
400
500
Label F lps (#)
Figure 1: Comparison of certified accuracy label-flipping poison attacks for our defense (SS-DPA algorithm) vs. Rosenfeld et al. (2020) on MNIST. Solid lines represent certified accuracy as a func- tion of attack size; dashed lines show the clean accuracies of each model. Our algorithm produces substantially higher certified accuracies. Curves for RRsenneed et al. (2020) are adapted from Figure in that work. The parameter q is hyperparameter Rosenfeld al. (2020)'s algorithm, and is a hyperparameter of our algorithm: the number of base classifiers in an ensemble.
model also includes any distortion to an sample and/or label in the training set - a distortion of training sample is simply the removal of the original sample followed by the insertion of the distorted sample. (Note that a sample distortion or label flip therefore increases the symmetric difference attack magnitude by two.)
Label-ffipping poisoning attacks: In this threat model, the adversary changes only the label for of m training samples. [Rosenfeld et al.) (2020) has recently provided certified defense for this threat model, which we improve upon.
In the last couple of years, certified defenses have been extensively studied for evasion attacks, where the adversary manipulates the test samples, rather than the training data (e.g. Wong & Kolter (2018); Gowal al. (2018); Lecuyer al. (2019); [Li al. (2018); [Salman al. (2019); Levine & Feizi (2020a b): Cohen et al. (2019), etc.) In the evasion case, certificate
lower bound on
the distance from the sample to the classifier's decision boundary: this guarantees that the sample's classification remains unchanged under adversarial distortions up to the certified magnitude.
Rosenfeld et al. (2000) provides an analogous certificate for label-flippig poisoning attacks: for an input sample x, the certificate of æ is a lower bound on the number of labels in the training set that would have to change in order to change the classification
æ Rosenfeld et al. 2020) 's
method is adaptation of certified defense for sparse (Lg) evasion attacks proposed by Lee
jet al. (201)). The adapted method for label-flipping attacks proposed by [Rosenfeld et al. (2020) is equivalent to randomly flipping each training label with fixed probability and taking consensus result. If implemented directly, this would require one to train a large ensemble of classifiers on different noisy versions of the training data. However, instead of actually doing this, Rosenfeld ett al.) (2020) focuses only on linear classifiers and is therefore able to analytically calculate the expected result. This gives deterministie, rather than probabilistic, certificates. Further, because Rosenfeld et al. (2020) considers a threat model where only labels are modified, they are able to train an unsupervised nonlinear feature extractor on the (unlabeled) training data before applying their technique, in order to learn more complex features.
Inspired by an improved provable defense against Lo evasion attacks (Levine Feizi, 2020a), in this paper, we develop certifiable defenses against general and label-flipping poisoning attacks that significantly outperform the current sfate-of-the-as certifiable defenses. In particular, we develop
Steinhardt et al. (017)) also refers to a "certified defense" for poisoning attacks. However, the definition of the certificate is substantially different in that work. which instead provides overall accuracy guarantees under the assumption that the training and test data are drawn from similar distributions, rather than providing guarantees for individual realized inputs.
2

---

Published as a conference paper at ICLR 2021
certifiable defense against general poisoning attacks called Deep Partition Aggregation (DPA) which is based on partitioning the training set into & partitions, with the partition assignment for training sample determined by hash function of the sample. The hash function can be any deterministic function that maps training sample to a partition assignment: the only requirement is that the hash value depends only on the value of the training sample t itself, that neither poisoning other samples, nor changing the total number of samples, nor reordering the samples can change the partition that t is assigned to. We then train k base classifiers separately, one on each partition. At the test time, we evaluate each of the base classifiers on the test sample a and return the plurality classification e as the final result. The key insight that removing a training sample, or adding a new sample, will only change the contents of one partition, and therefore will only affect the classification of one of the & base classifiers. This immediately leads to robustness certifications against general poisoning attacks which, to the best of our knowledge, is the first one of this kind.
If the adversary is restricted to flipping labels only (as Rosenfeld et al. (2020); we can achieve even larger certificates through a modified technique. In this setting, the unlabeled data is trustwor- thy: each base classifier in the ensemble can then make use of the entire training set without labels, but only has access to the labels in its partition. Thus, each base classifier can be trained as the entire dataset is available as unlabeled data, but only a very small number of labels are avail- able. This is precisely the problem statement of semi-supervised learning (Verma et al. 2019 Luo let al. 2018: Laine & Aila 2017] Kingma et al., 2014], Gidaris et al.] [2018). We can then leverage these existing semi-supervised learning techniques directly to improve the accuracies of the base classifiers in DPA. Furthermore, we can ensure that a particular (unlabeled) sample is assigned to the same partition regardless of label, so that only one partition is affected by a label flip (rather than possibly two). The resulting algorithm, Semi-Supervised Deep Partition Aggregation (SS-DPA) yields substantially increased certified accuracy against label-flipping attacks, compared to DPA alone and compared to the current state-of-the-art, Furthermore, while our method is de-randomized (as Rosenfeld et al. (2020) is) and therefore yields deterministic certificates, our technique does not require that the classification model be linear, allowing deep networks to be used.
On MNIST, SS-DPA substantially outperforms the existing state of the art (Rosenfeld et al. 2020) in defending against label-flip attacks: we certifyy at least half of images in the test set against attacks to over 600 (1. (1.0%) of the labels in the training set, while still maintaining over 93% accuracy (See Figure T and Table T]. In comparison, RRosenfeld et al. (2020)'s method achieves less than 60% clean accuracy on MNIST, and most test images cannot be certified with the correct class against attacks of even 200 label flips. We are also the first work to our knowledge to certify against general poisoning attacks, including insertions and deletions of new training images: in this domain, we can certify at least half of test images against attacks consisting of over 500 arbitrary training image insertions or deletions. On CIFAR-10, a substantially more difficult classification task, we can certify at least half of test images against label-flipping attacks on over 300 labels using SS-DPA (versus 175 label-flips for (Rosenfeld et al.) 2020)). and can certify at least half of test images against general poisoning attacks of up to nine insertions or deletions using DPA. To see how our method performs on datasets with larger numbers of classes, we also tested our methods on the German Traffic Sign Recognition Benchmark (Stallkamp et al. 2012), a task with 43 classes and on average 1000 samples per class. Here, we are able to certify at least half of test images as robust to 176 label flips, or 20 general poisoning attacks. These results establish new state-of-the-art in provable defenses against label-ffiping and general poisoning attacks.
2 RELATED WORKS
Levine & Feizi 2020a) propose randomized ablation technique to certifiably defend against sparse atatcks. Their method ablates some pixels, replacing them with a null value. Since it possible for the base classifier to distinguish exactly which pixels originate from æ. this results in more accurate base classifications and therefore substantially greater certified robustness than Lee et al. (2019). For example, on ImageNet, Lee al. (2019) certifies the median test image against distortions of one pixel, while Levine & Feizi (2020a) certifies against distortions of 16 pixels.
Our proposed method is related to classical ensemble approaches in machine learning, namely boot- strap aggregation and subset aggregation (Breiman 1996] Buja & Stuetzle| 2006;: Bühlmann 2003
Zaman & Hirose 2009). However, in these methods each base classifier in the ensemble trained
3

---

Published as a conference paper at ICLR 2021
on an independently sampled collection of points from the training set: multiple classifiers in the ensemble may be trained on (and therefore poisoned by) the same sample point, The purpose of these methods has typically been to improve generalization. Bootstrap aggregation has been pro- posed as an empirical defense against poisoning attacks (Biggio et al. 2011) as well as for evasion attacks (Smutz& & Stavrou (016). However, at the time of the initial distribution of this work, these techniques had not yet been used to provide certified robustness P Our unique partition aggregation variant provides deterministic robustness certificates against poisoning attacks. See Appendix Dor further discussion.
Weber et al. (2020) have recently proposed a different sandomizzed-mooothinn based defense against poisoning attacks by directly applying Cohen et al.] (2019)'s 's smoothing L2 evasion defense to the poisoning domain. The proposed technique can only certify for clean-label attacks (where only the existing samples in the dataset are modified, and not their labels), and the certificate guarantees robustness only to bounded L2 distortions of the training data, where the L.2 norm of the distortion is calculated across all pixels in the entire training set. Due to well-known limitations of dimensional scaling for smoothing based robustness certificates (Yang et al., 2020 Kumar et al., 2020 Blum et al. 2020), this yields certificates to only very small distortions of the training data. (For binary [I,00[[3,007 images]. ,. the maximum reported L2 certificate is 2 pixels.) Additionally, when using deep classifiers, WWberr al.] (2020) proposes randomized certificate, rather than a deterministic one, with a failure probability that decreases to zero only as the number of trained classifiers in an ensemble approaches infinity. Moreover, in Weber et al. (2020), unlike in our method, each classifier in the ensemble must be trained on a noisy version of the entire dataset. These issues hinder Weber al.] (2020)'s ss method be an effective scheme for certified robustness against poisoning attacks. After the initial distribution of this work, a recent revision of Rosenfeld et al. (2020) has suggested using randomised smoothing techniques on training samples, rather than just training labels, as a
general approach to poisoning defense. Both this work and Weber et al. (2020) could be considered as implementations of this idea, although this generalized proposal in Rosenfeld et al. (2020) does not include derandomization scheme (unlike Rosenfeld al. (2020)ss 's proposed derandomized defense against sabel-flipping attacks).
Other prior works have provided distributional, rather than pointwise guarantees against poisoning attacks. In these works, there is a tain level of average overall accuracy on test data, under the assumption that the test data and clean (pre-powt ppre-poisoning) training data are drawn from the same distribution. These works do not provide any guarantees that apply to specific test samples, however. As mentioned above, [Steinhartt et al.) (2017) provides such a distributional guarantee, specifically for a threat model of addition of poi- son samples. Other such works include [Sloan| (1995). which considers label-flipping attacks and determines conditions under which PAC-Icarning is possible in the presence of such attacks, and Bshouty et al. (2002) provides similar guarantees for replacement of samples. Other works (Di- akonikolas et al., 2016 Lai et al.) (016) provide distributional guarantees for unsupervised learning under poisoning attacks. Mahloujifar et al.] (2019) proposes provably effective poisoning attacks with high-probability pointwise guarantees of effectiveness on test samples. However, that work relies on properties of the distribution that the training set is drawn from. Diakonikolas et al. (2019) provide a robust training algorithm which provably approximates the clean trained model despite poisoning (rather than the behavior at a certain test point): this result also makes assumptions about the distribution of the clean training data.
guarantee that the classifier will achieve a cer-
3 PROPOSED METHODS
3.1 NOTATION
Let be the space of all possible unlabeled samples (i.c., the set of all possible images). We assume that it is possible to sort elements of S in deterministic, unambiguous way. In particular, in the case of image data, we can sort images lexicographically by pixel values: in general, any data that can be represented digitally will be sortable. We represent labels integers, so that the set of all possible labeled samples is S, = {xx, E S, e E NJ. A training set for a classifier is then represented
"In concurret work, Jia et al. 2020) consider using bootstrap aggregation directly for certified robustness. Their certificates are therefore probabilistic, and are not as large, in median, as the certificates reported here for MNIST and CIFAR-10.
4

---

Published as a conference paper at ICLR 2021
as T P(SL), where P(Sz) is the power set of SL. For t SL, we let sample(t) S refer to the (unlabeled) sample, and ltbel(t) E refer to the label. For a set of samples T E P(SL), we let samples(T) P(S) refer the set of unique unlabeled samples which occur in T. A classifier model is defined as a deterministic function from both the training set and the sample to be classified to label, i.e. f P(St) x S + N. We will use f(.) represent base classifier model (i.e., neural network), and g(-) to refer to a robust classifier (using DPA or SS-DPA),
Ae B represents the set symmetric difference between A and B: Ae = (A BBU A). The number of elements in A is AA, [n]] is the set of integers 1 through n,, and |z] is the largest integer less than or equal to 2. represents the indicator function: P otherwise. For a set A of sortable elements, we define Sort(A) as the sorted list of elements. For list of unique elements, for E I,, we will define index( as the index of in the list L..
1 if Prop is true; Pep
3.2 DPA
The Deep Partition Aggregation (DPA) algorithm requires base classifier model f P(SS) X + N, training set T E (.,r)), a deterministic hash function : Sr. - N, and hyperparameter
l E N indicating the number of base classifiers which will be used in the ensemble.
At the training time, the algorithm first uses the hash function h to define partitions Pl...., PB ST of the training set, as follows:
P : ((tt) = (mod k)}.
(1)
The hash function can be any deterministic function from St to N: however, it is preferable that the partitions roughly equal in size. Therefore we should choose an h which maps samples to a domain of integers significantly larger than k in a way such that h(.) (mod k)) will be roughly uniform over [R:]. In practice, for image data, we let h(t) be the sum of the pixel values in the image t.
Base classifiers are then trained each partition: define trained base classifiers fi S N as:
fi(x) == [(P.,
(2)
Finally, at the inference time, we evaluate the input on each base classification, and then count the number of classifiers which return each class:
(e(()) == Ki E [x) = c)|.
(3)
This lets us define the classifier which returns the consensus output of the ensemble:
Idpa (T, x) == arg max n..)
(4)
When taking the argmax, we break ties deterministically by returning the smaller class index. The resulting robust classifier has the following guarantee:
Theorem 1. For a fixed deterministic base classifier f. hash function h, ensemble size k, training set T, and input x. let:
c:= Idpa (T. xx)
p(x) The max. fa (c( + Loce)
(5)
2
Then, for any poisoned training set U. AFTTUR p(x), then Idpa (U,x) =c
All proofs are presented in Appendix A Note that T and U are unordered sets: therefore, in addition to providing certified robustness against insertions or deletions of training data, the robust classifier Idpa also invariant under re-ordering of the training data, provided that f has this invariance (which is implied, because ff maps deterministically from a set; see Section 3.2.1 for practical considera- tions). mentioned Section T DPA is a deterministic variant of randomized ablation (Levine & Feizi 2020a) adapted to the poisoning domain. Each base classifier ablates most of the training set, retaining only the samples in one partition. However, unlike in randomized ablation, the partitions are deterministic and use disjoint samples, rather than selecting them randomly and independently. In Appendix C we argue that our derandomization has little effect on the certified accuracies, while allowing for exact certificates using finite samples. We also discuss how this work relates to Levine & Feizi (2020c), which proposes a de-randomized ablation technique for a restricted class of sparse evasion attacks (patch adversarial attacks).
5

---

Published as a conference paper at ICLR 2021
3.2.1 DPA PRACTICAL IMPLEMENTATION DETAILS
One of the advantages of DPA is that we can use deep neural networks for the base classifier f. However, enforcing that the output of deep neural network is deterministic function of its training data, and specifically, its training data as an unordered set, requires some care. First, we must remove dependence on the order in which the training samples are read in. To do this, in each partition P, we sort the training samples prior to training, taking advantage of the assumption that S is well-ordered (and therefore Sz. S x N is also well ordered). In the case of the image data, this is implemented as a lexical sort by pixel values, with the labels concatenated to the samples as an additional value. The training procedure for the network, which is based on standard stochastic gradient descent, must also be made deterministic: in our PyTorch (Paszke et al. 2019) implementation, this can be accomplished by deterministically setting random seed at the start of training. As discussed in Appendix FJ we find that it is best for the final classifier accuracy to use different random seeds during training for each partition. This reduces the correlation in output between base classifiers in the ensemble. Thus, in practice, we use the partition index as the random seed (i.e., we train base classifier fa using random seed i.)
3.3 SS-DPA
Semi-Supervisse DPA (SS-DPA) is a defense against label-flip attacks. In SS-DPA, the base clas- sifier may be a semi-supervised learning algorithm: it can use the entire unlabeled training dataset, in addition to the labels for a partition. We will therefore define the base classifier to also accept an unlabelled dataset as input: f: P(S) x P(SL) x S + N. Additionally, our method of partitioning the data is modified both to ensure that changing the label of sample affects only one partition rather than possibly two, and to create a more equal distribution of samples between partitions.
First, we will sort the unlabeled data samples (T):
Tonnted := Sort (samleel)))))
For a sample t E T, note that index s sample(t)) is invariant under any dubel-fliping attack to T, and also under permutation of the training data they read. We now partition the data based on sorted index:
P. (t T index(Tsored: sample(t)) = (mod k)).
Note that in this partitioning scheme, we no longer need use a hash function h. Moreover, this scheme creates a more uniform distribution of samples between partitions, compared with the hash- ing scheme used in DPA. This can lead to improved certificates: see Appendix E This sorting-based partitioning is possible because the unlabeled samples are "clean", so we can rely on their order- ing, when sorted, to remain fixed. As DPA, we train base classifiers on each partition, this time additionally using the entire unlabeled training set:
(xx) (samples (T), P,,
(8)
The inference procedure is the same as in the standard DPA:
The (x) : Ki E [A]] fi (x) = c}
(9)
Issdpa (T' x)) == arg max (x)
The SS-DPA algorithm provides the following robustness guarantee against label-flippigg attacks 3
Theorem 2. For fixed deterministic semi-supervised base classifier f, ensemble size k training set T (with no repeated samples), and input x., let:
C = Irsdpu (T, x)),
p(x) = n. max to (nd + Tozol
(10)
2
For poisoned training set U obtuined by changing the labels of at most p samples in T, Issdpa (U,x) x)) = C.
'The theorem stated assumes that there are no repeated unlabeled samples (with different labels) in the training set T. This is reasonahle assumption, and in the alep-ffipping attack model, the attacker cannot cause this assumption he hroken. Without this assumption, the analysis is more complicated; see Appendix G
6

---

Published as a conference paper at ICLR 2021
Training set size
Number of Partitions
Median Certified Robustness
Base
Training
Clean
Classifier
time per Partition
Accuracy
Accuracy
1200
448
95.85%
76.97%
0.33 min
MNIST, DPA
60000
3000
509
93.36%
49.54%
0.27 min
1200
485
95.62%
80.77%
0.15 min
MNIST, SS-DPA
60000
3000
645
93.90%
57.65%
0.16 min
50
9
70.16%
56.39%
1.49 min
CIFAR, DPA
50000
250
5
55.65%
35.17%
0.58 min
1000
N/A
44.52%
23.20%
0,30 min
50
25
90.89%
89.06%
0.94 min
CIFAR, SS-DPA
50000
250
124
90.33%
86.25%
0.43 min
1000
392
89.02%
75.83%
0.33 min
50
20
89.20%
73.94%
2.64 min
GTSRB, DPA
39209
100
55.90%
35.64%
1.60 min
50
25
97.09%
96.35%
2.73 min
100
50
96.76%
94.96%
1.56 min
GTSRB, SS-DPA
39209
200
99
96.34%
91.54%
1.23 min
400
176
95.80%
83.60%
0.78 min
Summary statistics for DPA and SS-DPA algorithms on MNIST, CIFAR, and GTSRB. Median Certified Robustness is the attack magnitude (symmetric difference for DPA, label flips for SS-DPA) at which certified accuracy is 50%. Training times are on single GPU; note that many partitions can be trained in parallel. Note we observe some constant overhead time for training each classifier, so on MNIST, where the training time per image is small, & has little effect on the training time. For SS-DPA, training times do not include the time to train the unsupervised feature embedding (which must only be done once).
Table 1:
3.3. SEMI-SUPERVISED LEARNING METHOOSS FOR SS-DPA
In the standard DPA algorithm, we are able to train each classifier in the ensemble using only a small fraction of the training data; this means that each classifier can be trained relatively quickly: as the number of classifiers increases, the time to train each classifier can decrease (see Table I However, naive implementation of SS-DPA, Equation might suggest that training time will scale with k because each semi-supervised base classifier requires to be trained on the entire training set. Indeed, with many popular and highly effective choices of semi-supervised classification algorithms, such temporal ensembling (Laine & Aila (017). ICT (Verma et al. 2019). Teacher Graphs (Luo al. 2018) and generative approaches (Kingma et al. 2014), the main training loop trains on both labeled and unlabeled samples, so would see the total training time scale linearly with k. In order avoid this, we instead choose a semi-supervised training method where the unlabeled samples are used only learn semantic features of the data, before the labeled samples introduced: this allows us to use the unlabeled samples only once, and to then share the learned feature representations when training each base classifier. In our experiments, we choose RotNet (Gidaris al., 2018) for experiments on MNIST, and SimCLR (Chen et al. (020) for experiments on CIFAR- and GTSRB. Both methods learn an unsupervised embedding of the training set, on top of which all classifiers in the ensemble can be learned. Note that Rosenfeld et al. (2020) also uses SimCLR for CIFAR-10 experiments. As discussed in Section 3.2.1| we also sort the data prior to learning (including when learning unsupervised features), and set random seeds, in order to ensure determinism.
4 RESULTS
In this section, we present empirical results evaluating the performance of proposed methods, DPA and SS-DPA, against poison attacks MNIST, CIFAR-10, and GTSRB datasets. As discussed in Section I we use the RotNet architecture (Gidaris et al. 2018) for SS-DPA'S semi-supervised learning MNIST. Conveniently, the RotNet architecture is structured such that the feature extract- ing layers, combined with the final classification layers, together make up the Network-In-Netwee -n-Neworrk (NiN) architecture for the supervised classification (Lin et al. 2013). Therefore, MNIST,

---

Published as a conference paper at ICLR 2021
Label Fllps (Percent of Training Set)
8.
93
20
6.9
15
k 3001
k= 1200
k= 1200
Certifted Accuracy
Certied Accuracy
37-
07
26
35-
24-
24-
32
02
6:00
990
Attack Size (Symmetric Difference)
Label Flips (#)
(a) DPA (General poisoning attacks)
(b) SS-DPA (Label-flipping poisoning attacks)
Figure 2: Certified Accuracy to poisoning attacks on MNIST, using (a) DPA to certify against gen- eral poisoning attacks, and (b) SS-DPA to certify against label-flipping attacks. Dashed lines show the clean accuracies of each model.
use NiN for DPA's supervised training, and RotNet for SS-DPA's semi-supervised training. We use training parameters, for both the DPA (NiN) and SS-DPA (RotNet), directly from Gidaris et al. (0188) with a slight modification: we eliminate horizontal flips data augmentation, because hor- izontal alignment is semantically meaningful for digits On CIFAR-10 10 and GTSRB, we also use NiN (with full data augmentation for CIFAR-10, and without horizontal flips for GTSRB) for DPA experiments. For semi-supervised learning in SS-DPA, we use SimCLR (Chen et al.) 2020) for both datasets, as (Rosenfeld et al., 2020) does on CIFAR-10. SimCLR hyperparameters are provided in Appendix [ and additional details about processing the GTSRB dataset are provided in Appendix [ Note that for SimCLR we use linear classifiers as the final, supervised classifiers for each partition.
and are summarized in Table I Our metric, Certified Accu- racy as a function of attack magnitude wymmeeric-differeee or label-flips, refers to the fraction of samples which are both correctly classified and are certified robust to attacks of that magnitude. Note that different poisoning perturbations, which poison different sets of training samples, may be required to poison each test sample; i.e. we assume the attacker can use the attack budget separately for each test sample. Table [ also reports Median Certified Robustness, the attack magnitude to which at least 50% of the test set is provably robust.
Results are presented in Figures
Our SS-DPA method substantially outperforms the existing certificate (Rosenfeld et al. 2020) on label-flippigg attacks: in median, 392 label flips on CIFAR-10, versus 175; 645 label flips on MNIST. versus < 200. With DPA, we are also able to certify at least half of MNIST images to attacks of over 500 poisoning insertions or deletions, and can certify at least half of CIFAR-I0 im- ages to 9 poisoning insertions or deletions. On GTSRB, we can certify over half of images to 20 poisoning insertions or deletions, or 176 label flips. Note that this represents a substantially larger fraction of each class (each class has < 1000 training images on average) compared to certificates CIFAR- 10 (5000 training images per class). See Appendix H for additional experiments on GTSRB.
The hyperparameter & controls the number of classifiers in the ensemble: because each sample is used in training exactly one classifier, the average number of samples used to train each classifier is inversely proportional to k. Therefore, we observe that the base classifier accuracy (and therefore also the final ensemble classifier accuracy) decreases as is increased; see Table [ However, because the certificates described in Theorems | and 2 depend directly on the gap in the number of classifiers in the ensemble which output the top and runner-up classes, larger numbers of classifiers are necessary achieve large certificates. In fact, using & classifiers, the largest certified robustness possible is k/2. Thus, we see in Figures 2 and that larger values of l tend to produce larger robustness certificates. Therefore k controls trade-off between robustness and accuracy.
'In addition to the de-randomization changes mentioned in Section 3.2.1 we made one modification to the NiN 'baseline" for supervised learning: the baselin implementation in Gidaris et al. (2018), even when trained on small subset of the training data, uses normalization constants derived from the entire training set. This is (minor) error Gidari al. (2088) that we correct by calculating normalization constants on each subset.
8

---

Published as a conference paper at ICLR 2021
Label Fllps (Percent of Training Set)
92
24
66
10
[003
1000
k 250
k 250
k
Certmed Accuracy
37
0.7
35-
Certifted
24-
24
02
Attack Size (Symmetric Difference)
Label Flips (#)
(a) DPA (General poisoning attacks)
(b) SS-DPA (Label-flipping poisoning attacks)
Figure 3: Certified Accuracy to poisoning attacks on CIFAR, using (a) DPA to certify against general poisoning attacks, and (b) SS-DPA to certify against label-flipping attacks.
Label Flips (Percent of Training Set)
0.0
6.
23
a5
= 100
k 600
04
200
28
Certined Accuracy
k 100
Certined 24-
2.6
0.4
02-
Attack Size (Symmatric Difference)
Lobel Flips (#)
(a) DPA (General poisoning attacks)
(b) SS-DPA (Label-flipping poisoning attacks)
Figure 4: Certified Accuracy to poisoning attacks on GTSRB, using (a) DPA to certify against
general poisoning attacks, and (b) SS-DPA certify against label-flipping attacks.
Rosenfeld et al. (2020) also reports robustness certificates against label-flipping attacks binary MNIST classification, with classes and 7. Rosenfeld et al. (2020) reports clean-accuracy of 94.5% and certified accuracies for attack magnitudes up to 2000 label flips (out of 13007), with best certified accuracy less than 70%. By contrast, using a specialized form of SS-DPA, we are able to achieve clean accuracy of 95.5%, with every correctly-classifeed image certifiably robust up 5952 label flips (i.c. certified accuracy is also 95.5% at 5952 label flips.) See Appendix B for discussion.
CONCLUSION
In this paper, we described novel approach to provable defenses against poisoning attacks. Unlike previous techniques, our method both allows for exact, deterministic certificates and can be imple- mented using deep neural networks. These advantages allow us to outperform the current state-of- the-art on label-flip attacks, and develop the first certified defense against broadly defined class of general poisoning attacks.
ACKNOWLEDGEMEENS
This work was supported in part by NSF CAREER AWARD 1942230, HR 00111990077, HR 001 1 19S0026, NIST 6ONANB20D134 and Simons Fellowship "Foundations of Deep Learning."

---

Published as a conference paper at ICLR 2021
REFERENCES
Shun-ichi Amari, Naotake Fujita, and Shigeru Shinomoto. Four types of learning curves. Neural Computation, 4(4):605-618, 1992.
Battista Biggio, Igino Corona, Giorgio Fumera, Giorgio Giacinto, and Fabio Roli. Bagging classi- fiers for fighting poisoning attacks in adversarial classification tasks. In International workshop on multiple classifier systems, pp. 350-359. Springer, 2011.
Battista Biggio, Blaine Nelson, and Pavel Laskov. Poisoning attacks against support vector ma- chines. In Proceedings of the 29th International Coference on International Conference on Machine Learning, ICML' pp. 1467-1474, Madison, WI, USA, 2012. Omnipress. ISBN
9781450312851.
Avrim Blum, Travis Dick, Naren Manoj, and Hongyang Zhang. Random smoothing might be unable to certify Loo robustness for figh-dimenssonal images. arXiv preprint arXiv:2002.03517, 2020 2020.
Leo Breiman. Bagging predictors. Machine learning. 24(2):123-140, 1996.
Nader H. Bshouty, Nadav Eiron, and Eyal Kushilevitz. Pac learning with nasty noise. 288(2), 2002. ISSN 0304-3975. doi: 10. 0000106000044-977500000004444440
httpst pattps://dol. .rrg
10.1016/5033443395 00403-0
Peter Lukas Bühlmann. Bagging, subagging and bragging for improving some prediction algo- rithms. In Research report/Seminar für Statistik, Eidgenössische Technische Hochschule (ETII), volume 113. Seminar für Statistik, Fidgenössische Technische Hochschule (ETH), Zürich, 2003.
Andreas Buja and Werner Stuetzle. Observations on bagging. Statistica Sinica, pp. 323-351, 2006.
Ting Chen, Simon Korbblith, Mohammad Norouzi, and Geoffrey E. Hinton. A simple framework for contrastive learning of visual representations. ArXiv, abs/2002.05709, 2020.
Xinyun Chen, Chang Liu, Bo Li, Kimberly Lu, and Dawn Song. Targeted backdoor attacks on deep learning systems using data poisoning. arXiv preprint arXiv:1712.05526, 2017.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference Machine Learning, pp. 1310-1320, 2019.
I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart. Robust estima- tors in high dimensions without the computational intractability. In 2016 IEEE 57th An- nual Symposium Foundations of Computer Science (FOCS), pp. 655-664, Los Alamitos, CA, USA, oct 2016. IEEE Computer Society. doi: 10. RT200///OSS..0..... URL https: doii wtt.aaeeeeeeeurtrtooote.y...e..e wwtp//...10.////S...... 2016.
Ilias Diakonikolas, Gautam Kamath, D. Kane, Jerry Li, J. Steinhardt, and Alistair Stewart. Sever: A robust meta-algorithm for stochastic optimization. In ICML, 2019.
Spyros Gidaris, Praveer Singh, and Nikos Komodakis. Unsupervised representation learning by predicting image rotations. In International Conference on Learning Representations, 2018, URL.
htttps://openrevier net wtr. forrmmid==Svvw222
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Ue- sato, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint arXiv: 18100.18110120 12715, 2018.
Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong. Intrinsic certified robustness of bagging against data poisoning attacks, 2020.
Prannay Khosla, Piotr Teterwak, Chen Wang, Aaron Sarna, Yonglong Tian, Phillip Isola, Aaron Maschinot, Ce Liu, and Dilip Krishnan. Supervised contrastive learning. arXiv preprint arXiv:2004 / 1362, 2020.
10

---

Published as a conference paper at ICLR 2021
Durk P Kingma, Shakir Mohamed, Danilo Jimenez Rezende, and Max Welling. Semi- learning with deep generative models. In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems 27, pp. 338893 Curran Associates, Inc., 2014. URL / ps. 5352 sem aigprr/eeeeeeeeii.ie.tooooereeee
Aounon Kumar, Alexander Levine, Tom Goldstein, and Soheil Feizi. Curse of dimensionality on randomized smoothing for certifiable robustness. In International Conference on Machine Learn- ing. pp. 3458-5467. PMLR, 2020.
K. A. Lai, A. B. Rao, and Vempala. Agnostic estimation of mean and covariance. In 2016 IEEE 57th Annual Symposium Foundations of Computer Science (FOCS), pp. 665-674, 2016. doi: 10.1 1O/////CC..06....7
Samuli Laine and Timo Aila. Temporal ensembling for semi-supervised learning. In 5th Inter- national Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017. URL https: hatp::///penrrveiee http//pppeeeewweeeeeeeeeeeeeeeep http:/www.ee....eeeeeeeeeeee forum?
id BJBJJfo0fqge
M. Lecuyer, V. Atlidakis, Geambasu, D. Hsu. and S. Jana. Certified robustness to adversarial examples with differential privacy. In 20/9 2019 JEEE Symposium on Security and Privacy (SP), pp. 726-742, Los Alamitos, CA, USA, may 2019. IEEE Computer Society. doi: 10. 109/SP. 2019.00044 URL http:///......ecccooooerr.oorrrr 00044
20199.
Guang-He Lee, Yang Yuan, Shiyu Chang, and Tommi Jaakkola. Tight certificates of adversarial robustness for randomly smoothed classifiers. In Advances in Neural Information Processing Systems, pp. 491 1-4922, 2019.
Alexander Levine and Soheil Feizi. Robustness certificates for sparse adversarial attacks by ran- domized ablation. Association for the Advancement of Artificial Intelligence (AAAI), 2020a.
Alexander Levine and Soheil Feizi. Wasserstein smoothing: Certified robustness against wasser- stein adversarial attacks. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenty Third International Conference Arlificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 3938 -9988 PMLR, 26-28 Aug 2020b. URL httt:://proceediing
www.s.pres//vae www.0///eeeveeeeeeeeee html
Alexander Levine and Soheil Feizi (de) randomized smoothing for certifiable defense against patch attacks. Advances in Neural Information Processing Systems Foundation (NeurIPS), 2020c.
Bai Li. Changyou Chen, Wenlin Wang, and Lawrence Carin. Second-order adversarial attack and certifiable robustness. arXiv preprint 18Xiv:1809.03111 2018.
Min Lin, Qiang Chen, and Shuicheng Yan. Network in network. arXiv preprint arXiv:1312.4400, 2013.
Yucen Luo, Jun Zhu, Mengxi Li, Yong Ren, and Bo Zhang. Smooth neighbors on teacher graphs for semi-supervised learning. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018.
Saced Mahloujifar, Dimitrios I. Diochnos, and Mohammad Mahmoody. The curse of concentration in robust learning: Evasion and poisoning attacks from concentration of measure. Proceedings of the AAAI Conference on Artificial Intelligence. 33(01) (:436) 4543, Jul. 2019. doi: 10.1609/ aaai. v33101.3301153333
URL Itttps:// aaai. org/ www.a/orgggnnie.ddeeeeem
view /4373
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Crammunication-ffciiiin Learning of Deep Networks from Decentralized Data. volume 54 of Proceedings of Machine Learning Research, pp. 1273-1282, Fort Lauderdale, FL, USA, 20-22 Apr 2017. PMLR. httll//tt:///ttett
ml www.:presss..v. hwwc///mmmmaaaaaaaam 1a. html

---

Published as a conference paper at ICLR 2021
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 Vitito 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 (eds.), Advances in Neural Information Processing Systems 32, pp. 8024-8035. Curran Associates, Inc., 2019. URL http: http::///aaaaeeeeerr......cceaaa 901 htg.://cee.....taee..e.eeeeeoera pdf
ibrary.
Elan Rosenfeld, Ezra Winston, Pradeep Ravikumar, and Zico Kolter. Certified robustness to label- flipping attacks via randomized smoothing. arXiv preprint arXiv:2002.030/8, 2020.
Hadi Salman, Greg Yang. Jerry Li, Pengchuan Zhang, Huan Zhang, llya Razenshteyn, and Sebastien Bubeck. Provably robust deep learning via adversarially trained smoothed classifiers. arXiv preprint arXiv: 04584, 2019.
Ali Shafahi, W. Ronny Huang. Mahyar Najibi, Octavian Suciu, Christoph Studer, Tudor Dumitras, and Tom Goldstein. Poison frogs! targeted clean-label poisoning attacks on neural networks. In S. Bengio, H. Wallach, H. LLrochelle, K. Grauman, N. Cesa- Bianchi, and Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 6103-6113, Curran Associates, Inc., 2018. URL http: htst:::/papera.a. wwpp.cc/pappppe 7849 pels-poiioo---e frogs targogssttrggteedclleeele wwwecllaaanaaallllleeeae label poossll--tonnnnn-ttttaoo pdf
neura netwookkss
Robert H. Sloan. Four types of noise in data for pac learning.
Information Pro- doi: https//doi.org/10
cessing Letters, 54(3):157 162, 1995. ISSN 0020-0190.
1016/0020-0190 9095000166
URL http:// www.wsccinnedireet... http://ww...eeneeeeeeccco www. com/science/
article/pii/0222 00000990///110000000000000011111
Charles Smutz and Angelos Stavrou. When tree falls: Using diversity in en- semble classifiers to identify evasion in malware detectors. In 23rd Annual Nei- work and Distributed System Security Symposium, NDSS 2016, San Diego, Califor-
nia, USA, February 21-24, 2016. The Internet Society, 2016. URL http::/wpp
pdf
Stallkamp, M. Schlipsing, J. Salmen, and C. Igel. Man vs. computer: Benchmarking ma- chine learning algorithms for traffic sign recognition. Neural Networks, 32:323 332, 2012. ISSN 0893-6080. doi: (ct.://cceece//rrr/////////00330
URL http:://ww. Selected Pa-
sciencediree www.oo//cccc.co
pers from IJCNN 2011.
Jacob Steinhardt, Pang Wei W Koh, and Percy S Liang. Certified defenses for data poisoning attacks. In Advances in neural information processing systems, pp. 3517-3529, 2017.
Two Six Labs. Armory. https//giiubb.com/wssskbbbaaooon 2019.
Vikas Verma, Alex Lamb, Juho Kannala, Yoshua Bengio, and David Lopez-Paz. Interpolation sistency training for semi-supervised learning. Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 3635-3641. AAAI Press, 2019.
Maurice Weber, Xiaojun Xu, Bojan Karlas, Ce Zhang, and Li. Rab: Provable robustness against backdoor attacks. arXiv preprint arXiv:2003.08890 08904, 2020.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, pp. 5283-5292, 2018.
Han Xiao, Huang Xiao, and Claudia Eckert. Adversarial label flips attack support vector ma- chines. In Proceedings of the 20th European Conference on Artificial Intelligence, pp. 870-875, 2012.
12

---

Published as a conference paper at ICLR 2021
Greg Yang, Tony Duan, Edward Hu, Hadi Salman, 1lya Razenshteyn, and Jerry Li. Randomized smoothing all shapes and sizes. arXiv preprint arXiv:2002.08//8, 2020.
Faisal Zaman and Hideo Hirose. Effect of subsampling rate on subbagging and related ensembles of stable classifiers. In Santanu Chaudhury, Sushmita Mitra, C. A. Murthy, S. Sastry, and Sankar K. Pal (eds.). Pattern Recognition and Machine Intelligence, pp. 44-49, Berlin, Heidel- berg, 2009. Springer Berlin Heidelberg. ISBN 978-3-642-11166--8.
A PROOFS
Theorem 1. For fixed deterministic base classifier J, hash function ensemble size k, training set T, and input x, let:
c::= Odpa (T, ..)
ne max.
(c( m + dd<c)
(11)
p(x) ==
2
Then, for any poisoned training set U, Tf @ie p(x), we have: gdpa (U, = C.
Proof. We define the partitions, trained classifiers, and counts for each training set (T and U) as
described in the main text:
P.. = (t h(t) = (mod k)}
(12)
: Utt(t(((t) = (mod k}}
(x(x) I(P7,a0
(13)
(x) = S(P!" x))
no (x) = iii E [k]]s]] (x) = c?l
(14)
"c (z) = i E [*]] (a:) = cHl
1f
Idpa (Txx) == arg max n (x)
(15)
Idpa (U, .)) = arg max n (a:)
Note that here, we are using superscripts to explicitly distinguish between partitions (as well as base classifiers and counts) of the clean training set and the poisoned dataset (i.c, P is equivalent to P. in the main text). In Equation [3] as discussed in the main text, when taking the argmax, break ties deterministically by returning the smaller class index.
Note that P.T P! unless there is some t, with htt) i (mod k), in TUU. Because the mapping from / to l((l) (mod k)) is a deterministic function, the number of partitions i for which Pf * p! is at most [ e UJ, which is at most p(x). p7 = psd implies ff((x) ff (x), so the number of classifiers for which f. (w) # fl (x) is also at most p(æ). Then:
Vc' In - -n s p(ar).
(16)
Let c: Idpa (T) Note that Idpa (U, x) = =c iff:
AA < c: ni (x) > no (
AA > c: c: (x) 2 no (x:
where the separate cases from the deterministic selection of the smaller index in cases of ties
in Equation| 15 this can be condensed to v'' o c : n (x) > nL (x: leee- Then by triangle
inequality with Equation 16 we have that 9dpu (U, x) = ci # c: n (a) 2 (x) + 2p 1/
This condition is true by the definition of p(x)) Idpa (U, m)
13

---

Published as a conference paper at ICLR 2021
Theorem 2. For fixed deterministic cemi-supervised base classifier f, ensemble size k. training set T (with no repeated samples), and input H, let:
Drsdpa (T
max, C to (x) + 1c))
(17)
p(x)
2
For a poisoned training set U obtained by changing the labels of at most p samples in T,
Issdpa (U,z)
Proof. Recall the definition:
T := Sort(samples((T);
(18)
Because (T) = samples(U), we have Taoned = Usoned We can then define partitions and base classifiers for each training set (I' and U) described in the main text:
P.T {t T index iniee (Toonee, sample(t)) = (mod k)}
(19)
Pl (t U| index (T: someed sample(t))
(mod k)}
ff(x) (x) = (samples(T), P.T. ,))
(20)
1 (x) == (samples
Recall that for any t E T, Madex((ammed sample(t)) is invariant under label-flipping attack to T. Then, for each i, the samples in Pf will be the same as the samples in Pl possibly with some labels flipped. In particular, the functions (-) and f (-) will be identical, unless the label of
some sample with index sample(t)) = i (mod k)) has been changed. If at most p(x) labels
change, at most p(z) ensemble classifiers are affected: the rest of the proof proceeds similarly as that of Theorem 1.
B BINARY MNIST EXPERIMENTS
We perform a specialized instance of SS-DPA on the binary '1' versus '7' MNIST classification task. Specifically, we set m. that every partition receives only label. We first use 2-means clustering on the unlabeled data, to compute two means. This allows for each base classifier to use very simple "semi-supervised learning algorithm": if the test image and the one labeled training image provided to the base classifier belong to the same cluster, then the base classifier assigns the label of the training image the test image. Otherwise, it assigns the opposite label to the test image. Formally:
μ1, #22 Cluster centroids of samples(T)
1, || - #|12 I || - $|12
assignment(s) = 2, if I| a|12 > ||/| *|12
label(t.).
if assignment( assignment (t:)
fc(w)) ( [(samples (t:),
label(t,), if assignment(()) o assignment(t),
Note that each base classifier behaves exactly identically, up to a transpose of the labels: so in practice, we simply count the training samples which associate each of the two cluster centroids with each of the labels, and determine the number of label flips which would be required to change the consensus label assignments of the clusters. At the test time, each test image therefore needs to be processed only once. The amount time required for inference is then simply the time needed to calculate the distance from the test sample to each of the two clusters. This also means that every image has the same robustness certificate. able to achieve clean accuracy of 95.5%, with every robust up to 5952 label flips (i.c. certified accuracy is also 95.5% at 5952 label flips.) This means that the classifier is robust to adversarial label flips on 45.8% of the training data.
stated in the main text, using this method, claassfidd image certifiably
Rosenfeld et al. (2020) also reports robustness certificates against label-flipping attacks on binary MNIST classification with classes I and 7. Rosenfeld al. (2020) reports clean-accuracy of 94.5% and certified accuracies for attack magnitudes up to 2000 label flips (out of 13007: 15.4%), with the best certified accuracy less than 70%.
14

---

Published as a conference paper at ICLR 2021
C RELATIONSHIP TO RANDOMIZED ABLATION
As mentioned in Section I (SS-)DPA is in some sense related to Randomized Ablation (Levine) & Feizi, 2020a) (used in defense against sparse inference-time attacks) for training-time poisoning attacks. Randomized Ablation is certified defense against Lo (sparse) inference attacks, in which the final classification is a consensus among classifications of copies of the image. In each copy, fixed number of pixels are randomly ablated (replaced with null value). A direct application of Randomized Ablation to poisoning attacks would require each base classifier to trained on random subset of the training data, with each base classifier's 'ss training set chosen randomly and independently. Due to the randomized nature of this algorithm, estimation error would have to be considered in practice when applying Randomized Ablation using finite number of base classi- fiers: this decreases the certificates that can be reported, while also introducing a failure probability to the certificates. By contrast, in our algorithms, the partitions are deterministic and use disjoint, rather than independent, samples, In this section, we argue that our derandomization has little effect on the certified accuracies compared randomized ablation, even considering randomized ablation with no estimation еπтоr (i.e., with infinite base classifiers). In the poisoning case specifically, using additional base classifiers is expensive because they must each be trained so one would observe large estimation error when using realistic number of base classifiers. Therefore our derandom- ization can potentially improve the certificates which can be reported, while also allowing for exact certificates using finite number of base classifiers.
For simplicity, consider the label-flipingg case. In this case, the training set has fixed size, m. Thus, Randomized Ablation bounds can be considered directly. A direct adaptation of Levine & Feizi (2020a) would, for each base classifier, choose s out of m samples to retain labels for, and would ablate the labels for the rest of the training data. Suppose For each base classifier, the probability that a flipped label is used in classification (and therefore that the base classifier is 'poisoned") is:
adversary has flipped labels.
Pr(poisoned)RA = 1
(21)
where "RA" stands for Randomized Ablation.
In this direct adaptation, one must then use a very large ensemble of randomized classifiers. The ensemble must be large enough that we can estimate with high confidence the probabilities (on the distribution of possible choices of training labels to retain) that the base classifier selects each class. If the gap between the highest and the next-highest class probabilities can be determined to be greater than 2 Pr(poisoned)) RA. then the consensus classification cannot be changed by flipping r labels. This is because, at worst, every poisoned classifier could switch the highest-class classification to the runner-up class, reducing the gap by at most 2 Pr(poisoned).
Note that this estimation relies on each base classifier using a subset of labels selected randomly and independently from the other base classifier. In contrast, our SS-DPA method selects each subset disjointly. If r labels are flipped, assuming that in the worst case each flipped label is in a different partition, using the union bound, the proportion of base classifiers which can be poisoned is
Pr(poisoned)ss:DpA J
rs
(22)
m
where for simplicity we assume that evenly divides the number of samples m, so m/k labels are kept by each partition. Again we need the gap in class probabilities to be at least 2 Pr(poisoned)ss-Des to ensure robustness. While the use of the union bound might suggest that our deterministic scheme (Fquation 22) might lead to a significantly looser bound than that of the probabilistic certificate (Fquation p1). this is not the case in practice where r8 << m. For exam- plc, in MNIST-sized dataset (m 60000), using s 50 labels per base classifier, to certify for r = 200 label flips, we have Pr(poisoned)RA = 0.154, and (r(poisoned)ss.ong derandomization only sightly increases the required gap between the top two class probabilities.
< 0.167. The
To understand this, note that if the number of poisonings r is small compared to the number of par- titions k then even if the partitions are random and independent, the chance that any two poisonings occur in the same partition is quite small. In that case, the union bound in Equation (2) is actually quite close an independence assumption. By accepting this small increase in the upper bound of
15

---

Published as a conference paper at ICLR 2021
the probability that each base classification is poisoned, our method provides all of the benefits of de-randomization, including allowing for exact robustness certificates using only a finite number of classifiers. Additionally, note that in the Randomized Ablation case, the empirical gap in estimated class probabilities must be somewhat larger than Pr(poisonedJRA in order to certify robustness with high confidence, due to estimation error: the gap required increases more the number of base classifiers decreases. This is particularly important in the poisoning case, because training a large number of classifiers is substantially more expensive than performing large number of evaluations, as in randomized smoothing for evasion attacks.
We also note that Levine & Feizi (2020c) also used a de-randomized scheme based on Random- ized Ablation to certifiably defend against evasion patch attacks. However, in that work. the de- randomization does not involve a union bound over arbitrary partitions of the vulnerable inputs. Instead, in the case of patch attacks. the attack is geometrically constrained: the image is therefore divided into geometric regions (bands or blocks) such that the attacker will only overlap with fixed number of these regions. Each base classifier then uses only a single region to make its classifica- tion. Levine & Feizi (2020c) do not apply this to derandomization via disjoint subsets/union bound to defend against poison attacks. Also, we note that we borrow from Levine & Feizi (2020c) the deterministic "tie-breaking" technique when evaluating the consensus class in Equation which can increase our robustness certificate by up one.
D RELATIONSHIP TO EXISTING ENSEMBLE METHODS
As mentioned in Section [ our proposed method is related to classical ensemble approaches in machine learning, namely bootstrap aggregation ( ("bagging") and subset aggregation ("subagging")) (Breiman 1996. Buja & Stuetzle, 2006 Bühlmann [003] Zaman & Hirose 2209). In these meth- ods, each base classifier in the ensemble is trained on an independently sampled collection of points from the training set: this means that multiple classifiers in the ensemble may be trained on the same sample point. The purpose of these methods has typically been to improve generalization, and therefore to improve test set accuracy: bagging and subagging decrease the variance component of the classifier's s error.
In subagging. each training set for a base classifier is an independently sampled subset of the train- ing data: this is in fact an identical formulation to the "direct Randomized Ablation" approach discussed in Appendix C However, in practice, the size of each training subset has typically been quite large: the bias error term increases with decreasing subsample sizes (Buja & Stuetzle (006). Thus, the optimal subsample size for maximum accuracy is large: Bühlmann (2003) recommends using s m/2 samples per classifier "hallf-uubagging"" with theoretical justification for optimal generalization. This would not be useful in Randomized Ablation-like certification, because any one poisoned element would affect half of the ensemble. Indeed, in our certifiably robust classifiers, observe a trade-off between accuracy and certified robustness: our use of many very small partitions clearly not optimal for the test-set accuracy [Table
In bagging, the samples in each base classifier training set are chosen with replacement, so elements may be repeated in the training "set" for single base classifier. Bagging has been proposed as an empirical defense against poisoning attacks (Biggio et al., 2011) as well as for evasion attacks (Smutz& & Stavrou| 2016). However, to our knowledge, these techniques have not yet been used to provide certified robustness.
Our approach also bears some similarity to Federated Averaging (McMahan et al. 2017 in that base models are trained on disjoint partitions of the dataset. However, in Federated Averaging, the model weights of many distributed base classifiers are periodically averaged and re-distributed during learning, in order to allow for efficient massively-paralle learning. No theoretical robustness guarantees are provided (as this is not the goal of the algorithm) and it would seem difficult to derive them, given that the relationship between model weights and final classification is highly non-line non-linear in deep networks. By contrast, DPA uses the consensus of final outputs after all base classifiers are trained independently (or, in the SS-DPA case, independently for labeled data).
16

---

Published as a conference paper at ICLR 2021
Number Partitions
Median
Base Classifier
Certified
Clean
k
Robustness
Accuracy
Accuracy
Hash
Sort
Hash
Sort
Hash
Sort
1200
460
485
95.74%
95.62%
78.64%
80.77% %
MNIST, SS-DPA
3000
606
645
93.87%
93.90%
55.04%
57.65 %
50
25
25
90.90%
90.89%
89.00%
89.06%
CIFAR, SS-DPA
250
124
124
90.36%
90.33%
86.34%
86.25%
1000
387
392
89.11 %
89.02%
75.35%
75.83%
50
25
25
96.98%
97.09%
96.33%
96.35 %
100
50
50
96.79 %
96.76%
94.86%
94.96 %
GTSRB, SS-DPA
200
99
99
96.38 %
96.34%
91.39%
91.54 %
400
174
176
95.89 %
95.80%
83.07%
83.60% %
Table 2: Comparison of SS-DPA with hashing ('Hash' columns, described in Appendix E to the SS-DPA algorithm with partitions determined by sorting ('Sort' columns, described in the main text). Note that partitioning via sorting consistently results in higher base classifier accuracies, and can increase (and never decreases) median certified robustness. These effects seem to be larger on MNIST than on CIFAR-10.
E SS-DPA WITH HASHING
It is possible to use hashing, as in DPA, in order to partition data for SS-DPA: as long as the hash function htt does not use the sample label in assigning a class (as ours indeed does not), will always assign image to the same partition regardless of label-flipping, so only one partition will be affected by a label-flip. Therefore, the SS-DPA label-fiipping certificate should still be correct. However, explained in the main text, treating the unlabeled data trustworthy allows to partition the samples evenly among partitions using sorting. This motivated by the classical un- derstanding in machine learning (e.g. Amari al. 1992)) that learning curves (the test error versus the number of samples that a classifier is trained on) tend to be convex-like. The test error of a base classifier is then approximately a convex function of that base classifier's partition size. Therefore, the partition size is a random variable, by Jensen's 's inequality, the expected test error of the (random) partition size is greater than the test error of the mean partition size. Setting all base classifiers to use the mean number of samples should then maximize the average base classifier accuracy. To validate this reasoning, we tested SS-DPA with partitions determined by hashing (using the same partitions as we used in DPA), rather than the sorting method described in the main text. See Table 2 for results. As expected, the average base classifier accuracy decreased in most (8/9) experiments when using the DPA hashing, compared using the sorting method of SS-DPA. However, the effect was minimal in CIFAR- 10 and GTSRB experiments: the main advantage of the sorting method was seen MNIST. This is partly because we used more partitions, and hence fewer average samples per partition, in the MNIST experiments: fewer average samples per partition creates a greater variation in the number of samples per partition in the hashing method. However, CIFAR-10 with 1000 and MNIST with & = 1200 both average 50 samples per partition, but the base classifier accuracy difference still was much more significant on MNIST (2.13%) compared to CIFAR- 10 (0.48%).
On the MNIST experiments, where the base classifier accuracy gap was observed, we also saw that the effect of hashing on the smoothed classifier was mainly decrease the certified robustness, and that there was not a significant effect on the clean smoothed classifier accuracy. As discussed in Appendix F this may imply that the outputs of the base classifiers using the sorting method are more correlated, in addition to being more accurate.
F EFFECT OF RANDOM SEED SELECTION
mention that we "deterministically" choose different random seeds for training each partition, rather than training every partition with the same random seed. To see a comparison between using distinct and the same random seed for each partition, Table 3 Note that there is not a large, consistent effect across experiments on either the base classifier accuracy nor the the median certified robustness: however, in most experiments, the distinct random seeds resulted in
In Section 3.2.
17

---

Published as a conference paper at ICLR 2021
Number of Partitions k
Median Certified
Base
Clean
Classifier
Robustness
Accuracy
Accuracy
Same
Distinct
Same
Distinet
Same
Distinet
1200
443
448
95.33%
95.85
76.21%
76.97%
MNIST, DPA
3000
513
509
92.90%
93.36 %
49.52%
49.54%
1200
501
485
94.45%
95.62% %
82.31 %
80.77%
MNIST, SS-DPA
3000
663
645
91.60%
93.90 %
59.33%
57.65%
50
70.14%
70.16%
56.13%
56.39%
CIFAR, DPA
250
5
5
55.24%
55.65%
34.96%
35.17%
1000
N/A
N/A
43.96%
44.52%
23.14%
23.20%
50
25
25
90.92%
90.89%
89.08%
89.06%
CIEAR, SS-DPA
250
124
124
90.25%
90.33%
86.25%
86.25%
1000
391
392
88.97%
89.02%
75.82%
75.83%
50
20
20
88.59%
89.20 %
73.89%
73.94%
GTSRB, DPA
100
54.98%
55.90 %
34.74%
35.64%
50
25
25
97.06%
97.09% %
96.36%
96.35%
100
50
50
96.79%
96.76%
94.95%
94.96%
GTSRB, SS-DPA
200
99
96.34% %
96.34%
91.54%
91.54%
400
176
176
95.85%
95.80%
83.64%
83.60%
Table 3: Comparison of DPA and SS-DPA algorithms using the same random seed for each partition ("Same' columns, described in Appendix [F) to the DPA and SS-DPA algorithms using the distinct random seeds for each partition ('Distinct" columns, described in the main text). Note that using distinct random seeds usually results in higher smoothed classifier clean accuracies, and always does so when using DPA.
higher smoothed classifier accuracies. This effect was particularly pronounced using SS-DPA on using distinct seeds increased smoothed accuracy by least 1% each value of k on MNIST. This implies that shared random seeds make the base classifiers more correlated with each other: at the same level of average base classifier accuracy, classifiers will all misclassify the same sample (If the base classifiers were perfectly uncorrelated, we would see nearly 100% smoothed clean accuracy wherever the base classifier accuracy was over 50%. Also if they were perfectly correlated, the smoothed clean accuracy would equal the base classifier accuracy). Interestingly, the base classifier accuracy was significantly lower for both SS- DPA/MNIST experiments when using diverse random seeds; this defies any obvious explanation. However, this does make the correlation effect even more significant: for example, for = 3000, the SS-DPA smoothed classifier accuracy is over 2% larger with distinct seeds, despite the fact that the base classifier is over 1% less accurate.
MNIST:
more likely that a plurality base
It somewhat surprising that the base classifiers become correlated when using the seed, given that they are trained on entirely distinct data. However, two factors may be at play here. First, note that the random seed used in training controls the random cropping of training images: it is possible that, because the training sets of the base classifiers are so small, using the same cropping patterns in every classifier would create a systematic bias.
random
Note that the effect was least significant for SS-DPA on CIFAR-IO and GTSRB, with SimCLR. This may be due the final supervised classifiers being linear classifiers, rather than deep networks, for these experiments.
G SS-DPA WITH REPEATED UNLABELED DATA
The definition of training set that we use, T P(St), technically allows for repeated samples with differing labels: there could be pair of distinct samples, t, T, such that sample(t) sample(t'), but label(t) + (t'). This creates difficulties with the definition the label-flipping attack: for example, the attacker could flip the label of t become the label of t': this would break the definition of T as a set. In most applications, this is not a circumstance that warrants practical consideration: indeed, none of the datasets used in experiments have such instances (nor can
18

---

Published as a conference paper at ICLR 2021
Number of Partitions k
Median Certified Robustness
Base Classifier
Clean
Accuracy
Accuracy
Equal.
Equal
Equal.
50
23
20
91.84%
89.20%
80.98%
73.94% 35.64%
GTSRB, DPA
100
77.81 %
55.90%
54.83%
Table 4: Comparison of DPA algorithm with and without using histogram equalization prepro- cessing on the GTSRB dataset. We find that histogram equalization substantially improves perfor- mance when 100, although the effect is more modest k 50.
label-fliping attacks create them), and therefore. for performance reasons, our implementation of SS-DPA does not handle these cases. Specifically, to optimize for performance, we verify that there are no repeated sample values, and then sort T itself (rather than samples(T)) lexicographically by image pixel values: this is equívalent to sorting (amples("") if no repeated images occur which we have already verified - and avoids an unnecessary lookup procedure to find the sorted index of the unlabeled sample for each labeled sample. However, the SS-DPA algorithm described in Section can be implemented to handle such datasets, under a formalism label- bhbl-ffipping tailored to represent this edge case.
Specifically, we define the space of possible labeled data points as S = x P(N): each labeled data point consists of sample along with set of associated labels. We then restrict dataset T to be any subset of Sy such that for all t, E T, sample(t) o sample(t'). In other words, we do allow repeated sample values I as formally defined: if repeated samples exist, one can simply merge their sets of associated labels (in the formalism).
Note that using this definition, the size of T will equal the size of samples(T). and the samples will always remain the same: the adversary can only modify the label sets of samples "in place". SS-DPA will always assign an unlabeled sample, along with all of its associated labels, to the same partition, regardless of any label flipping. In practice, this is because, as described in Section 3.3 the partition assignment of a labeled sample depends only on its sample value, not its label: all labeled samples with the same sample value will be put in the same partition. Note that this is true even if the implementation represents two identical sample values with different labels as two separate samples: one does not actually have implement labels sets. Therefore, any changes to any labels associated with a sample will only change the output of one base classifier, so all such changes can together be considered single label-flip in the context of the certificate. In the above formalism, the certificate represents the number of samples in T whose label sets have been "flipped": i.e., modified in any way.
H GTSRB WITH HISTOGRAM EQUALIZATION
Because GTSRB contains images with widely varying lighting conditions, histogram equalization is sometimes applied as a preprocessing step when training classifiers on this dataset (for example,Twwy Six Labs (2019)) We tested this preprocessing with DPA. and found that it substantially improved the performance for larger & (A: = 100). However, for A = 50, which had larger accuracy and median certified robustness with or without this preprocessing, the effect was modest (a 2.64% increase in clean accuracy, and an increase of 3 in certified robustness). The greater effect when & is large likely because each partition contains fewer images of each class, so more likely for each base classifier that some lighting conditions are not represented in the training data for every class. Applying histogram equalization to the training and test data reduces this effect.
I SIMCLR EXPERIMENTAL DETAILS
We used the PyTorch implementation of SimCLR provided by Khosla et al. (2020). with modifica- tions to ensure determinism described in the main text. For training the embeddings, used ResNet18 model with batch size of 512 for CIFAR-10 and 256 for GTSRB, initial learning rate of 0.5, cosine annealing, and temperature parameter of 0.5, and trained for 1000 epochs. For learning
19

---

Published as a conference paper at ICLR 2021
the linear ensemble classifiers, we used batch size of 512, initial learning rate of 1.0, and trained for 100 epochs.
J GTSRB DATASET DETAILS
The GTSRB dataset consists images of variable sizes, from x to 250 X 250. We resized all images to 48 x 48 during training and testing (using bilinear interpolation). However, wanted to ensure that our certificates still applied correctly to the original images. In particular, for SS-DPA, sort the dataset using pixel values of the original image, with black padding for smaller images. This ensures that repeated images do not occur in the original dataset, (as described in Appendix G) even if the resized images could possibly contain repeats. For DPA, we hash using the sum of all pixels in the original image. Finally, for sorting to ensure determinism in training, we use the images after resizing (ensuring no repeated images is not important for this). For both NiN and SimCLR training, we excluded horizontal flips from data augmentation and contrastive learning, because some classes in GTSRB are in fact mirror-images other classes.
20


Reviews:
[{"review_id": "y2p6HMUtGom", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Context and summary of the results:\n\nData poisoning attacks deal with adversaries who change the training set, up to a certain degree (controlled in different ways), with the aim of lowering the \"quality\" of the produced model. Previously methods were designed to tolerate adversarial perturbations while preserving low risk in the produced model.\n\nThis paper studies point-wise certification methods for the decision made on a test instances against data poisoning.  Namely, for a given point, we would like to know: how many changes in the training set would still lead to the same produced label. Knowing this result gives confidence about the predicted label, even if some poisoning has already happened (to a certain degree). Exhaustive search (on various cases of data and retraining) would not be possible, and a theoretically sound algorithmic method would be necessary.\n\nThis paper proposes a general, simple, yet effective idea for certification in poisoning context: partition the input data into a bunch of subsets and then train sub-models on them independently; then output the majority of the predictions. It is not hard to see that if the majority vote is far by amount alpha from the 2nd majority vote, then one can certify up to alpha/2 changes in the training set. To make this proposal formal, there are some subtleties that the paper handles by using hash functions to do the partition (so that the order of the elements won’t affect which subset they land). This approach is indeed reminiscent of \"Bagging\" (Bootstrap Aggregating), but this seems to be the first work (along with concurrent cited works) that apply this to certification under poisoning attacks. \n\nOther than studying “general” poisoning attacks (in which changes in the data set are measured by Hamming distance), the paper further applies the idea to the special case of label-flip attacks, which were previously studied by Rosenstein et al. as well, but this work shows how to improve their bound through the experiments on popular data sets quite strongly. Along the way, (for label flipping) there are some neat ideas also to improve the results and the efficiency. (1) The paper shows how to benefit from semi-supervised learning by each of the sub-models is still trained on the *whole* data set, while only a subset of the samples (i.e., those in a particular partition) would have the labels kept. (2) To make this scalable, the paper carefully picks the semi-supervised method in such a way that all trainings of sub-models share the same 1st step of dealing with non-labeled data (on the *whole* data set).\n \nTo evaluate: Certification of decisions under poisoning is a very recent and important direction. The results of this work are convincing as they improve the bounds achieved in previous work quite strongly. The methods used here, though seemingly simple in the hindsight, are sound and might be applicable in other settings as well. The paper is written quite clearly. I, therefore, recommend acceptance.\n\nComments:\n\nThe paper mentions that \n\"Rosenfeld et al. (2020) does not provide a provable defense for this more general case.\"\nHowever, it seems the latest version of this previous work of Rosenstein et al. (from Aug'20 - 2nd paragraph of section 4) actually did propose a method for \"general\" poisoning attacks using randomized smoothing as well, even though they only applied the idea concretely only to label flipping. So, even though it is not quite clear how their exact certification bounds would be, and also the result would be randomized certification as opposed to deterministic, which is the result of this paper, I still think this previous work on general poisoning certification shall be mentioned as well.\n\nSome related works: The exact noise models studied in this paper are actually studied long ago in classical learning papers that, unfortunately, do not get to be cited in recent works in poisoning attacks much. It is true that those works are not about certification, but the basic problem of provable learning under poisoning/noise are essentially the same. Citation [1] below defined the label flip noise model, and [2] defined the \"general\" poisoning model in which the adversary can change a fraction of the data. The current paper actually uses a more fine-grained version that distinguishes between add/removes, but this is the same as measuring Hamming distance up to a factor 2. Works [3,4] also initiated a computationally efficient approach to dealing with poisoning attacks in a provable way, and [6] particularly studied supervised learning and poisoning-robust SGC. Of course, I understand that here we want an extra certification on top of the defense, yet I still think the line of work on provable defenses against poisoning are closely related. Also, I think your work (and similar certified robustness papers on general poisoning) can be interpreted as \"certified poisoning against *targeted* poisoning\" because you certify the decisions for each individual test instance. So, they seem to complement \"provable attacks\" on targeted poisoning e.g., from [5] in which it is shown how to increase the error close to one for a particular test instance if the original error (without attack) is a not-so-small probability to begin with. It seems one difference between the two settings is that the attack of [5] needs a bigger poisoning budget to succeed and you certify a smaller number (naturally) but I think a comparison with the complementary line of work is needed as well.\n\nI also think that the comparison with Steinhardt et al. is better to be expanded a bit more. Both papers use the term \"certified robustness\" but as (correctly) mentioned in the paper, the two settings are not the same (e.g., here the certification is for a test instance rather than the model). I think it is better to bring this note out of a footnote and shed more light on this helpful comparison to prevent confusion for readers.\n\nI know that the experiments are done with image datasets, but the problem studied in this work is more general, and it would have been probably better if the treatment of the issue was also as such (e.g., the abstract mentions \"bounded number of images\", though it could be basically any piece of data).\n\n\nCitations:\n\n[1] Sloan, Robert H. \"Four types of noise in data for PAC learning.\" Information Processing Letters, 1995.\n\n[2] Bshouty, Nader H., Nadav Eiron, and Eyal Kushilevitz. \"PAC learning with nasty noise.\" Theoretical Computer Science 2002.\n\n[3] Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. \"Robust estimators in high dimensions without the computational intractability.\" FOCS, 2016\n\n[4] Kevin A Lai, Anup B Rao, and Santosh Vempala. \"Agnostic estimation of mean and covariance.\" FOCS 2016.\n\n[5] Mahloujifar Saeed, Dimitrios I. Diochnos, and Mohammad Mahmoody. \"The curse of concentration in robust learning: Evasion and poisoning attacks from concentration of measure.\" AAAI 2019.\n\n[6] Diakonikolas, I., Kamath, G., Kane, D., Li, J., Steinhardt, J., & Stewart, A. \"Sever: A robust meta-algorithm for stochastic optimization.\" ICML. 2019.\n\n*********** post rebuttal comment ************\n\nThanks for the comments and clarifiactions.\nJust to add that: I agree that Rosenfeld et al (2020)'s work on general poisoning is concurrent to yours (as that part is expanded in sub-sequent updates to their Arxiv, not the original ICML paper).  And anyway the bounds of this submission are stronger. Yet, I think that a brief discussion/comparison with this aspect of the  Rosenfeld et al (2020) paper is helpful to the reader.", "extra_scores": {}, "extra_text": {}}, {"review_id": "EJlP-O_-mLZ", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "**Pros:**\n+ The paper is clearly written and easy to follow.\n+ Provides some certifiable measure of robustness against general poisoning attacks\n\n**Cons:**\n- The extremely simplistic defense strategy that is utilized implies that the defense has very poor performance. On the CIFAR-10 dataset, the drop in clean accuracy is >20% but only around 9 samples out of 50,000 can be certified robust. These results consider a very weak attacker poisoning less than 50 samples out of 50,000. Thus, while defense may claim to provide some certified robustness against general poisoning attacks, the results are not promising. There is also no discussion of how the defense can be improved.\n- The proof of theorem 1 appears to be a missing a critical piece, which is the determination of how the quantity $\\rho(x)$ was actually computed.", "extra_scores": {}, "extra_text": {}}, {"review_id": "BKWc7xVl-2p", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper studies how to enhance the robustness of classifiers in face of data poisoning attacks. The key insight of the paper is that adding or deleting one training point can at most change one of the k partitions of the training set. Based on this idea, the authors propose Deep Partition Aggregation (DPA), a robust classification algorithm that first partitions the training data into k subsets, and then separately train a model on each subset. The final prediction is an aggregation of the predictions of those k classifiers using the majority vote. Apart from DPA, the authors also consider a setting where a large amount of data points do not have labels. In that scenario, semi-supervised learning algorithms are used as based algorithm when training separate models on each subset. The proposed method SS-DPA enjoys the property of being fast to train, since learning is performed on a subset that has smaller number of data points. The paper derives theoretical guarantees in terms of when the prediction of a particular data point can be certifiably correct. Finally, experiments on MNIST and CIFAR demonstrate the effectiveness of the proposed defense as compared to prior works.\n\nThe main advantage of the paper lies in the experimental part. Empirically, the proposed method indeed shows strong defense ability against poisoning attacks. For example, on the MNIST dataset, more than half of the test images can be certified with DPA. Furthermore, by comparison with prior works, the authors show that the proposed DPA and SS-DPA are better at defending against data poisoning attacks.\n\nOne disadvantage of the paper is that the power of the attacker in this paper seems to be very weak. For example, for MNIST, the attacker only changes the label of 1% training data. However, even with such a small fraction of change, the proposed DPA already suffers 0 certified accuracy. This is a bit disappointing because 1% does not seem to be a large fraction. I am wondering if the authors could justify that 1% poisoning in practice is already a significant amount of change to the training data, thus is unlikely to happen in the real world. That will convince me that the proposed defense is indeed useful for a real-world scenario.\n\nApart from the basic DPA, the paper also proposed another algorithm SS-DPA that applies when there is a large number of unlabeled data points, i.e., a semi-supervised learning setting. I am wondering to what extend unlabeled helps with improving the certified robustness? From a theoretical perspective, the classification is only about the discriminative part of the data distribution, and there is theory in semi-supervised learning that suggests using unlabeled data points do not substantially improve the accuracy, e.g., the following paper\n\nDoes Unlabeled Data Provably Help?\nWorst-case Analysis of the Sample Complexity of Semi-Supervised Learning \n\nThus I am wondering if the authors could explain why unlabeled data points should be used in the defense problem?\nTheorem 1 and Theorem 2 look pretty much the same. I am wondering if the difference only lies in the baseline classifier, one being supervised and the other being semi-supervised? If so, I think the authors should consider merging the two theorems, as they are not quite different from each other.\n\nFinally, it is not clear how to pick the parameter k, i.e., the number of partitions. The experimental results seem to suggest that the larger k is, the better robustness guarantee we will have. However, k cannot go to infinitely large. One has to at least ensure that each base classifier has decent accuracy, which requires a reasonably large number of training data in each partition. Therefore, k cannot be too large. I am wondering if the authors could provide some empirical guidance regarding how to pick k?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "5y9B88cQVeI", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper proposes to solve two variants of adversarial poisoning attacks: 1) General Poisoning Attacks - where either the input is distorted or the label is flipped. 2) Label Flipping Poisoning Attacks - where the input images are intact but only the labels are flipped. The crux of the algorithm is the standard ensemble model idea, where we train multiple models each with a partition of the data and take the most prevalent prediction among all models during inference. This naturally adds robustness to the Additionally, the paper also provides theoretical lower bounds on the 'amount' of distortion below which precision is preserved.\n\nFor the case of general poisoning attacks, the paper proposes a certified defense against the cardinality of the symmetric distance of the original training dataset and the poisoned dataset (including both image distortion and/or label flips). For the special case of label-flip attacks only, the certification follows Rosenfeld et al. 2020 where we quantify the minimum number of label flips required to change the prediction of a particular sample point. \n\nThe algorithm for the general poisoning case (called DPA - Deep Partition Aggregation) is simple. Just assign each training sample to one of K partitions based on a random hash function. Then train K classifiers on their respective data subsets. During inference, we just need to get a label prediction from each of the K models and get the mode of all those predictions. \n\nWhen the attacks are restricted to just label flips, we can simply invoke semi-supervised learning. For each of the K models, we can first train an unsupervised model on the entire training data (since inputs are not corrupted). This will map inputs to a nice semantic space without any label information. Then the partitioned data labels can be used to train individual models like before. Any label flip can only effect one of the K models. Hence, the inference is robust as it is an aggregation over several models.\n\nThe results on MNIST and CIFAR are very encouraging and SOTA as per the papers claims.\n\nPros:\n1. strong experimental results\n2. paper clearly written with nice introduction to types of attacks.\n3. Theoretical bounds on tolerance to adversarial attacks.\n\nCons:\n1. Similarities with federated learning methods - I've some novelty concerns. Federated Averaging (McMahan et al. 2017) hinges on a very similar idea of partitioning labels (not disjointly but with some overlap). SO the novelty here seems to be only the application?\n2. How abt evasion attacks? - There is no discussion about how this method tackles evasion attacks or what prevents it from tackling it. \n3. repetitive plots- Figure 1 plots are reappearing in Figure 2. It is good for a reader but might make the paper look less substantial.\n4. fairly simple idea - notwithstanding the federated averaging idea, ensemble methods are common in several walks of ML. For example,  (Medini et. al. 2019, NeurIPS), uses random hash functions to create label partitions to train with 50 MM labels. even the concept of using the model number as a random seed to avoid correlations seems to be prevalent in that paper. Infact, feature hashing and JL-Lemma literature use it in and out. \n5. might warrant experiments on more datasets", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors develop a novel strategy, Deep Partition Aggregation, to train models to be certifiably robust to data poisoning attacks based on flipping labels of a small subset of the training data or introducing poisoned input features. They improve upon existing certified defences against data poisoning and are the first to establish certified guarantees against general poisoning attacks.

Most reviewers were in support of acceptance. Reviewer concerns were raised in the rebuttal phase but were convincingly addressed in the rebuttal phase. One reviewer did raise concerns on the weakness of experimental results on CIFAR-10, but the fact that this method has established the first certified defence in the general poisoning setting and that the results are stronger on other datasets certainly warrant acceptance. I would encourage the authors to clarify this in the final version.


Decision: Accept (Poster)