summaries: This paper proposes momentum of memorization as a way to distinguish hard examples needed for efficient learning from noisy examples which decrease classification accuracy. The method finds confident, hard examples and updates them dynamically during model training. This is done by iteratively selecting examples with labels that agree with model predictions and then training on only the confident data. Results show improved accuracy on standard image classification datasets with both synthetic and real world label noise.

summaries: This paper propose a novel and effective method called Me-Momentum to cope with noisy labels. The algorithm borrows the idea of momentum from physics and tries to identify hard examples. The authors alternately update the hard examples and improve the classifier to achieve the robustness to noisy labels. Experiments and comparisons with recent state-of-art methods are provided to verify the effectiveness of Me-Momentum.

summaries: The authors introduce an interesting approach to handling hard "confident" samples in learning with label noises. At the heart of the proposed approach is an interactive method that jointly refines the classifier and the samples. The confident samples are initialized by utilizing the memorization effect of deep networks. Then, a classifier is learned from such samples.

abstractText: Examples that are close to the decision boundary—that we term hard examples, are essential to shaping accurate classifiers. Extracting confident examples has been widely studied in the community of learning with noisy labels. However, it remains elusive how to extract hard confident examples from the noisy training data. In this paper, we propose a deep learning paradigm to solve this problem, which is built on the memorization effect of deep neural networks that they would first learn simple patterns, i.e., which are defined by these shared by multiple training examples. To extract hard confident examples that contain non-simple patterns and are entangled with the inaccurately labeled examples, we borrow the idea of momentum from physics. Specifically, we alternately update the confident examples and refine the classifier. Note that the extracted confident examples in the previous round can be exploited to learn a better classifier and that the better classifier will help identify better (and hard) confident examples. We call the approach the “Momentum of Memorization” (Me-Momentum). Empirical results on benchmark-simulated and real-world label-noise data illustrate the effectiveness of Me-Momentum for extracting hard confident examples, leading to better classification performance.

authors:
Dana Angluin
Philip Laird

title: Learning from noisy examples

venue: Machine Learning,

authors:
Devansh Arpit
Stanisław Jastrzębski
Nicolas Ballas
David Krueger
Emmanuel Bengio
Maxinder S Kanwal
Tegan Maharaj
Asja Fischer
Aaron Courville
Yoshua Bengio

title: A closer look at memorization in deep networks

venue: In ICML,

authors:
Yoshua Bengio
Jérôme Louradour
Ronan Collobert
Jason Weston

title: Curriculum learning

venue: In ICML, pp

authors:
Pengfei Chen
Ben Ben Liao
Guangyong Chen
Shengyu Zhang

title: Understanding and utilizing deep neural networks trained with noisy labels

authors:
Jiacheng Cheng
Tongliang Liu
Kotagiri Ramamohanarao
Dacheng Tao

title: Learning with bounded instance-and label-dependent label noise

authors:
Mark Dredze
Koby Crammer
Fernando Pereira

title: Confidence-weighted linear classification

title: Shake-shake regularization

venue: arXiv preprint arXiv:1705.07485,

authors:
Jacob Goldberger
Ehud Ben-Reuven

title: Training deep neural-networks using a noise adaptation layer

venue: In ICLR,

authors:
Sheng Guo
Weilin Huang
Haozhi Zhang
Chenfan Zhuang
Dengke Dong
Matthew R Scott
Dinglong Huang

title: Curriculumnet: Weakly supervised learning from large-scale web images

venue: In ECCV,

authors:
Bo Han
Jiangchao Yao
Gang Niu
Mingyuan Zhou
Ivor Tsang
Ya Zhang
Masashi Sugiyama

title: Masking: A new perspective of noisy supervision

venue: In NeurIPS,

authors:
Bo Han
Quanming Yao
Xingrui Yu
Gang Niu
Miao Xu
Weihua Hu
Ivor Tsang
Masashi Sugiyama

title: Co-teaching: Robust training of deep neural networks with extremely noisy labels

authors:
Warren He
Bo Li
Dawn Song

title: Decision boundary analysis of adversarial examples

authors:
Sheng-Jun Huang
Rong Jin
Zhi-Hua Zhou

title: Active learning by querying informative and representative examples

venue: In NeurIPS, pp

authors:
Lu Jiang
Zhengyuan Zhou
Thomas Leung
Li-Jia Li
Li Fei-Fei

title: MentorNet: Learning datadriven curriculum for very deep neural networks on corrupted labels

authors:
Jan Kremer
Fei Sha
Christian Igel

title: Robust active label correction

venue: In AISTATS,

title: Learning multiple layers of features from tiny images

venue: Technical report,

authors:
M Pawan Kumar
Benjamin Packer
Daphne Koller

title: Self-paced learning for latent variable models

authors:
Yann LeCun
Corinna Cortes
Christopher J.C. Burges

title: The MNIST database of handwritten digits

authors:
Mingchen Li
Mahdi Soltanolkotabi
Samet Oymak

title: Gradient descent with early stopping is provably robust to label noise for overparameterized neural networks

authors:
Yuncheng Li
Jianchao Yang
Yale Song
Liangliang Cao
Jiebo Luo
Li-Jia Li

title: Learning from noisy labels with distillation

venue: In ICCV,

authors:
Tongliang Liu
Dacheng Tao

title: Classification with noisy labels by importance reweighting

venue: IEEE Transactions on pattern analysis and machine intelligence,

authors:
Yang Liu
Hongyi Guo

title: Peer loss functions: Learning from noisy labels without knowing noise rates

authors:
Xingjun Ma
Yisen Wang
Michael E Houle
Shuo Zhou
Sarah M Erfani
Shu-Tao Xia
Sudanthi Wijewickrema
James Bailey

title: Dimensionality-driven learning with noisy labels

authors:
Laurens van der Maaten
Geoffrey Hinton

title: Visualizing data using t-sne

venue: Journal of machine learning research,

authors:
Eran Malach
Shai Shalev-Shwartz

title: Decoupling" when to update" from" how to update

authors:
Mehryar Mohri
Afshin Rostamizadeh
Ameet Talwalkar

title: Foundations of Machine Learning

authors:
Nagarajan Natarajan
Inderjit S Dhillon
Pradeep K Ravikumar
Ambuj Tewari

title: Learning with noisy labels

authors:
Tam Nguyen
C Mummadi
T Ngo
L Beggel
Thomas Brox

title: SELF: learning to filter noisy labels with self-ensembling

authors:
Curtis G Northcutt
Tailin Wu
Isaac L Chuang

title: Learning with confident examples: Rank pruning for robust classification with noisy labels

authors:
Giorgio Patrini
Alessandro Rozza
Aditya Krishna Menon
Richard Nock
Lizhen Qu

title: Making deep neural networks robust to label noise: A loss correction approach

venue: In CVPR,

authors:
Scott E Reed
Honglak Lee
Dragomir Anguelov
Christian Szegedy
Dumitru Erhan
Andrew Rabinovich

title: Training deep neural networks on noisy labels with bootstrapping

authors:
Mengye Ren
Wenyuan Zeng
Bin Yang
Raquel Urtasun

title: Learning to reweight examples for robust deep learning

title: A rate of convergence for mixture proportion estimation, with application to learning from noisy labels

venue: In AISTATS, pp

authors:
Hwanjun Song
Minseok Kim
Dongmin Park
Jae-Gil Lee

title: Prestopping: How does early stopping help generalization against label noise

authors:
Ilya Sutskever
James Martens
George Dahl
Geoffrey Hinton

title: On the importance of initialization and momentum in deep learning

authors:
Daiki Tanaka
Daiki Ikami
Toshihiko Yamasaki
Kiyoharu Aizawa

title: Joint optimization framework for learning with noisy labels

authors:
Antti Tarvainen
Harri Valpola

title: Mean teachers are better role models: Weight-averaged consistency targets improve semi-supervised deep learning results

authors:
Kiran K Thekumparampil
Ashish Khetan
Zinan Lin
Sewoong Oh

title: Robustness of conditional gans to noisy labels

authors:
Sunil Thulasidasan
Tanmoy Bhattacharya
Jeff Bilmes
Gopinath Chennupati
Jamal MohdYusof

title: Combating label noise in deep learning using abstention

title: Toward robustness against label noise in training deep discriminative neural networks

title: The nature of statistical learning theory

venue: Springer science & business media,

authors:
Andreas Veit
Neil Alldrin
Gal Chechik
Ivan Krasin
Abhinav Gupta
Serge Belongie

title: Learning from noisy large-scale datasets with minimal supervision

authors:
Yixin Wang
Alp Kucukelbir
David M Blei

title: Robust probabilistic modeling with bayesian data reweighting

authors:
Xiaobo Xia
Tongliang Liu
Nannan Wang
Bo Han
Chen Gong
Gang Niu
Masashi Sugiyama

title: Are anchor points really indispensable in label-noise learning

authors:
Xiaobo Xia
Tongliang Liu
Bo Han
Nannan Wang
Mingming Gong
Haifeng Liu
Gang Niu
Dacheng Tao
Masashi Sugiyama

title: Parts-dependent label noise: Towards instance-dependent label noise

authors:
Tong Xiao
Tian Xia
Yi Yang
Chang Huang
Xiaogang Wang

title: Learning from massive noisy labeled data for image classification

authors:
Yilun Xu
Peng Cao
Yuqing Kong
Yizhou Wang

title: L_dmi: A novel information-theoretic loss function for training deep nets robust to label noise

authors:
Xingrui Yu
Bo Han
Jiangchao Yao
Gang Niu
Ivor W Tsang
Masashi Sugiyama

title: How does disagreement benefit co-teaching

authors:
Xiyu Yu
Tongliang Liu
Mingming Gong
Dacheng Tao

title: Learning with biased complementary labels

authors:
Chiyuan Zhang
Samy Bengio
Moritz Hardt
Benjamin Recht
Oriol Vinyals

title: Understanding deep learning requires rethinking generalization

authors:
Zhilu Zhang
Mert Sabuncu

title: Generalized cross entropy loss for training deep neural networks with noisy labels

heading: 1 INTRODUCTION

text:
As training datasets are growing big while accurately labeling them is often expensive or sometimes even infeasible, cheap datasets with label noise are ubiquitous in many real-world applications. Without any care, label noise will degenerate the performance of learning algorithms, especially for these based on deep neural networks (Zhang et al., 2017). Learning with noisy labels (Angluin & Laird, 1988) aims to reduce the side-effect of label noise and therefore has become an important topic in machine learning.
Existing methods for learning with noisy labels can be divided into two categories: algorithms that result in statistically consistent or inconsistent classifiers. Methods in the first category intent to design classifier-consistent algorithms (Zhang & Sabuncu, 2018; Kremer et al., 2018; Liu & Tao, 2016; Scott, 2015; Natarajan et al., 2013; Goldberger & Ben-Reuven, 2017; Patrini et al., 2017; Thekumparampil et al., 2018; Yu et al., 2018; Liu & Guo, 2020; Xu et al., 2019), where classifiers learned by using the noisy data will statistically converge to the optimal classifiers defined by clean data. However, these methods rely heavily on the noise transition matrix (Liu & Tao, 2016; Patrini et al., 2017; Xia et al., 2019). In real-world applications, it is hard to learn the instance-independent noise transition matrix (Cheng et al., 2020). To be free of estimating the noise transition matrix, methods in the second category employ heuristics to reduce the side-effect of label noise (Yu et al., 2019; Han et al., 2018b; Malach & Shalev-Shwartz, 2017; Ren et al., 2018; Jiang et al., 2018; Ma et al., 2018; Kremer et al., 2018; Tanaka et al., 2018; Reed et al., 2015; Han et al., 2018a; Guo et al., 2018; Veit et al., 2017; Vahdat, 2017; Li et al., 2017; 2020). These methods were reported to empirically work well, especially in the setting of instance-dependent label noise.
One promising direction in the second category is to extract examples with clean labels—confident examples— (Northcutt et al., 2017; Cheng et al., 2020; Chen et al., 2019; Malach & Shalev-Shwartz, 2017; Han et al., 2018b; Yu et al., 2019; Thulasidasan et al., 2019; Nguyen et al., 2020; Dredze et al., 2008; Liu & Tao, 2016; Wang et al., 2017; Ren et al., 2018; Jiang et al., 2018). The idea is that compared with the original noisy training data, the extracted examples are less noisy and thus
will lead to a classifier with better performance. Given only noisy data, state-of-the-art methods exploit the memorization effect (Zhang et al., 2017; Arpit et al., 2017) to extract confident examples. The memorization effect will enable deep neural networks to first learn patterns that are shared by majority training examples. As clean labels are of majority in each noisy class (Natarajan et al., 2013; Xiao et al., 2015), deep neural networks would therefore first fit training data with clean labels, and then gradually fit the examples with incorrect labels (Chen et al., 2019). Therefore, early stopping (Li et al., 2020; Song et al., 2019) and the small loss trick (Jiang et al., 2018; Han et al., 2018b; Yu et al., 2019) can be used to exploit confident examples.
Examples that are close to the decision boundary are called hard examples. As illustrated in Figure 1, hard (confident) examples play an important role in shaping the decision boundary. It has also been widely studied in the traditional classification problem that hard examples are essential to train accurate classifiers (Vapnik, 2013; Bengio et al., 2009; Huang et al., 2010; He et al., 2018). Notwithstanding the importance of hard confident examples, none of the existing methods studies how to extract hard confident examples from noisy data. Note that extracting hard confident examples is non-effortless. Since hard examples are often of a small proportion and contain less discriminative information compared with the easy ones (these that are far away from the decision boundary), they are often entangled with inaccurately labeled examples in the procedures of extraction.
In this paper, by alternately updating the confident examples and refining the classifier, we propose a deep learning paradigm that is able to extract hard confident examples from the noisy training data, leading to better classification performance. Specifically, the idea is similar to the usage of momentum from physics. As stated in the statistical learning theory, with better training data, better classifier can be obtained (Mohri et al., 2018). We can then think of the classifier as a particle traveling through the hypothesis space, getting acceleration from the confident data. Classifiers with better performance can be achieved by properly exploiting the previously extracted confident examples. This is similar to the momentum trick used in optimization that previous gradient information can be used to escape local minimum and achieve fast convergence rates (Sutskever et al., 2013)1. At a high level, the proposed method is built on the memorization effect of deep neural networks and on the intuition that better confident examples will result in a better classifier and that a better classifier will identify better confident examples (and hard confident examples). The proposed method is therefore called the Momentum of Memorization (Me-Momentum).
We conduct experiments to show the effectiveness of the proposed Me-Momentum on noisy versions of MNIST, CIFAR10, CIFAR100, and a real-world label noise dataset Clothing1M. Specifically, on MNIST and CIFAR, we generate class- and instance-dependent label noise and visualize the extracted hard confident examples, which justifies why Me-Momentum consistently outperforms the baseline methods. Codes will be available online.

heading: 2 ME-MOMENTUM

text:
In this section, by specifying the proposed method of momentum of memorization (Me-Momentum; summarized in Algorithm 1), we would like to detail how to accomplish extracting hard confident
1In optimisation, the parameter vector can be thought of as a particle traveling through the parameter space, getting acceleration from the gradient of the loss. The momentum trick demonstrated that gradient in previous update can help escape local minimum and achieve fast convergence rates.
Algorithm 1 Me-Momentum Input: Noisy training data, noisy validation data, iteration number Ninner and Nouter; Output: Extracted confident examples and the classifier; 1: Initialize a classifier f0 by using the noisy training data and early stopping; //memorization effect for i = 1, . . . , Nouter do
for j = 1, . . . , Ninner do 2: Update the extracted confident examples;
//i.e., the training examples whose noisy labels are identical to the ones predicted by fj−1 3: Obtain the classifier fj ;
//initialize the network by using the parameters of fj−1 and train it by employing confident examples; the classifier fj will be chosen with the highest noisy validation accuracy throughout the training procedure 4: Break and output fj−1 if the highest validation accuracy is non-increasing in the loop;
end 5: Re-initialize a classifier f0;
//randomly initialize the network and train it by using confident examples; the classifier f0 will be chosen with the highest noisy validation accuracy throughout the training procedure 6: Break and output fj−1 if the highest validation accuracy is non-increasing in the loop;
end
examples and boosting the classification performances. At the high level, by alternately updating the confident examples and refining the classifier, Me-Momentum fulfils a positive cycle that better confident examples will result in a better classifier and that a better classifier will identify better confident examples. Specifically, Me-Momentum has two loops, i.e., an inner loop and an outer loop. In the inner loop, Me-Momentum alternates update of the confident examples and classifier (Steps 2 and 3). However, the inner loop continually refines a classifier and thus depends heavily on the initialization of the classifier (Step 1). It may lead to the memorization of noisy labels and the inferiority of sample-selection bias. To handle this problem, the outer loop re-initialize the classifier (Step 5) while maintains the previously extracted confident examples.
There are some points to be clarified for the proposed Algorithm 1: Q1. How to initialize a good classifier in Step 1? Q2. How to extract confident examples in Step 2? Q3. How to validate the learned classifiers in Steps 3 and 5 without a clean validation set? Q4. Why the proposed method is called Me-Momentum? Q5. Why hard confident examples can be extracted?
To answer the first question, we would like to mention that the aim of the initialization in Step 1 is to initialize a good classifier for the positive cycle: a better classifier will identify better confident examples and better confident examples will result in a better classifier. A good candidate should have a fairly high classification accuracy, e.g., higher than random guessing. Otherwise, the positive cycle cannot be evoked. Fortunately, the initialization can be made by exploiting the memorization effect of deep neural networks that they would first fit clean data (Arpit et al., 2017; Zhang et al., 2017). Note that this memorization effect is independent of training optimization or network backbones (Arpit et al., 2017). Specifically, we use the early stopping trick. For easy understanding, we would like to introduce a definition of high-peak. A noisy validation accuracy at the i-th epoch is called an i-th high-peak if it achieves the highest accuracy in the epoch range {1, . . . , i}. Assume the i-th and j-th high-peaks occur next to each other, having noisy validation accuracies of a and b, respectively. The training early stops if (b − a)/(j − i) ≤ τ , where τ is a hyper-parameter. In the experiments, we set τ = 0.1, which empirically works well across all datasets. In Appendix A, we compare the difference between the early stopping method and the traditional validation method; We also study the sensitivity of the hyper-parameter.
The answer to the second question is closely related to the memorization effect. Note that the classifier initialized in Step 1 would fit the clean data well but not the incorrectly labeled data because of the memorization effect and early stopping. Therefore, we can treat the training examples whose noisy labels are identical to the ones predicted by the classifier obtained in Step 1 as confident examples. This also applies for the classifiers in Step 3 to extract confident examples, which are
iteratively trained by employing the updated confident data. Note that there are some other feasible methods to extract confident examples, e.g., extract those who have a large class posterior.
In Step 3, we aim to learn a better classifier compared with the one in the previous round. This can be achieved because of two reasons: (1) we initialize the network with the parameters of the classifier learned in the previous round; (2) we have a better set of confident examples as the training sample. This starts the positive cycle that better confident examples will result in a better classifier and that a better classifier will identify better confident examples. The third question is essential for identifying the classifiers in the cycle. Note that the accurately labeled examples are always assumed to be dominant in each class in the community of learning with noisy labels (Natarajan et al., 2013; Liu & Tao, 2016; Han et al., 2018b). Otherwise, the true class label cannot be identified by only exploiting the noisy data. This assumption implies that the performance on the noisy validation set (split from the noisy training set) and these on test set are positively correlated. The noisy validation set could be used as a surrogate to validate the classifiers if no clean validation set is available. We therefore validate the classifiers in Steps 3 and 5 with the highest noisy validation accuracies during the training. Empirical results show that it works well.
To answer the fourth question, we would like to first mention that the proposed method heavily relies on the memorization effect of deep neural networks. Specifically, in Step 1, a classifier is initialized by exploiting the memorization effect via early stopping, which is used to identity confident examples. Later, the classifier and confident examples are iteratively refined and updated, respectively, which is the positive cycle we have mentioned before. Note that this cycle also depends on the memorization effect to update confident examples and refine classifiers. Our method is named as momentum of memorization (Me-Momentum) because it also uses the trick of momentum to better exploit the memorization effect. Specifically, we can think of the classifier as a particle traveling through the hypothesis space, getting acceleration from the updated extracted confident data. We exploit the previously extracted confident examples to help learn a better classifier, i.e., initializing the network by using the parameters of the classifier trained with the confident examples extracted in the previous round. The impact of the confident examples in a certain round will decay as we continue updating the classifier.
We intuitively answer the fifth question by employing Figure 2. Hard confident examples will be progressively extracted also due to the momentum trick, i.e., previously extracted confident examples will help identify hard confident examples. Specifically, in Figure 2(a), we show the noisy training examples, where circles and triangles represent two classes respectively and the red ones denote the examples with incorrect labels. Let the dash line in Figure 2(b) denote a classifier learned by Me-Momentum. We can use it to extract confident examples, e.g., the green circles and blue triangles, according to Step 2 of Algorithm 1. Compared with Figure 1(a), we can see that hard confident examples close to the optimal boundary, i.e., the circle and triangles with red edges, will be extracted. Note that as better and better classifiers will be learned by Me-Momentum, more
and more hard confident examples will be extracted. An visualization is shown in Figure 4.
Relation to existing work: The strategy of alternatively optimizing the classifier and updating the training examples is not new for dealing with label noise. For example, Joint Optim (Tanaka et al., 2018), Co-teaching (Han et al., 2018b; Yu et al., 2019), and SELF (Nguyen et al., 2020) are similar to ours. Specifically, Joint Optim and Co-teaching update the classifier with one step of stochastic gradient descent while SELF and the proposed method refine the classifier to be optimal with respect to the extracted confident examples. However, existing methods have not focused on extracting hard confident examples and thus are substantially different from this paper because they neglected the importance of avoiding the accumulated error caused by the single initialization of the classifier and the sample-selection bias. Experiments (e.g., Figures 3 and 4) show that Me-Momentum with the outer loop part (i.e., re-initialization of the classifier) contributes significantly to extracting hard confident examples and achieving high label precision. Note that without employing the ensemble technique, SELF is a special case of Me-Momentum with only the inner loop part. We avoid to integrate the ensemble technique to the proposed method for simplicity and clarity.
Me-Momentum is similar to curriculum learning as it also learns from easy to difficult. However, curriculum learning needs a predefined curriculum (sample weighting scheme), e.g., assigning big/small wights for confident/noisy data. If the curriculum is not available, some clean data is required to learn a mentornet to provide a curriculum (Jiang et al., 2018) or a latent variable could be introduced by self-paced learning (Kumar et al., 2010) to learn a curriculum. Differently, MeMomentum only based on noisy data and does not explicitly learn a curriculum. Me-Momentum also has a similar flavor to active learning which tends to choose and label hard examples to learn from at each iteration. However, for active learning, no label information is available before the data is chosen while Me-Momentum has noisy labels and have to consider the side-effect of label noise.

heading: 3 EXPERIMENTS

text:
Datasets: To verify the effectiveness of the proposed method, we do experiments on datasets with both synthetic and real-world label noise. Specifically, we manually corrupt MNIST (LeCun et al., 1998), CIFAR10, and CIFAR100 (Krizhevsky, 2009) with class-dependent label noise and instancedependent label noise. We detail how to generate class-dependent and instance-dependent label noise in the supplementary material. We employ the real-world noisy dataset Clothing1M (Xiao et al., 2015). These datasets have been widely used in studies with noisy labels (Han et al., 2018b; Tanaka et al., 2018; Xia et al., 2019).
For MNIST, CIFAR10, and CIFAR100, we leave out 10% of the noisy training data as noisy validation data. Clothing1M contains one million noisy training images, which are crawled from shopping websites, labeling by surrounding text. Almost all existing work uses the 14k clean validation data in their experiments. To verify the robustness of the proposed method, we also employ noisy validation data in our experiments. Specifically, 100k noisy data are randomly left as noisy validation data and the remaining 900k noisy data as the training data.
Baselines: Me-Momentum is compared against the following state-of-the-art approaches. (1) Statistically consistent methods: Forward (Patrini et al., 2017), T-revision (Xia et al., 2019), and DMI (Xu et al., 2019); (2) Statistically inconsistent methods: Decoupling (Malach & Shalev-Shwartz, 2017), MentorNet (Jiang et al., 2018), Co-teaching (Han et al., 2018b), Joint Optim (Tanaka et al., 2018), SELF (Nguyen et al., 2020) where MentorNet, Co-teaching and SELF use the idea of extracting confident examples by employing the small loss trick.
Network structure and optimization: All the methods are implemented with default parameters by PyTorch v1.5. For the experiments on MNIST, CIFAR10, and CIFAR100, we set Ninner = 20, Nouter = 3, and follow the settings of T-revision (Xia et al., 2019). Specifically, LeNet-5, ResNet18 and ResNet-34 networks are used for MNIST, CIFAR10 and CIFAR100 respectively. We use SGD with momentum 0.9, weight decay 10−4, batch size 128, and an initial learning rate of 10−2, divided by 10 after the 40-th epoch and 80-th epoch respectively (we fix the learning rate of 10−2 for the early stopping method). Data augmentation is used with horizontal random flips and 32× 32 random crops after padding 4 pixels on each side. For Clothing1M, a ResNet-50 is used. We set Ninner = 6 and Nouter = 3. To show the effectiveness of the proposed method, we do experiments by randomly initializing the network and pre-training it by employing ImageNet, respectively. As the noisy training sample contains a large number of examples, we train the network for 5 epochs and choose the best one with the highest classification accuracy on the noisy validation set. We use SGD with momentum 0.9, weight decay 10−3, batch size 32, with a learning rate of 5×10−3, and divided it by 10 at the 3-rd and 5-th round in the inner loop. For each outer loop, the model will be randomly re-initialized (or replaced by a pre-trained one). The learning rate will be reset to 5×10−3. For data augmentation, all images are resized to 256 × 256, horizontal random flipped, and cropped in the middle with a size of 224× 224. Note that due to the page limit, some complementary experiments to Sections 3.1 and 3.2 and comparison with SELF are put in the Appendix.

heading: 3.1 VERIFY MOMENTUM OF MEMORIZATION

text:
In Section 2, we discussed that Me-Momentum is implemented by fulfilling the positive cycle that better confident examples will result in a better classifier and that a better classifier will identify
better confident examples. In this subsection, we will empirically verify this positive cycle, which can be done on the synthetic datasets as we have their ground-truth labels.
In Figure 3, we can see that in the inner loops (e.g., rounds 0-5, rounds 6-9, and rounds 10-12 in the first column of figures represent three inner loops respectively), the classification accuracy generally increases (note that the figures are not smooth because the classifiers are tested on the unseen test data) and the number of extracted confident examples clearly increases (although their label precision decreases slightly). We can also see that in the outer loops (e.g., rounds 0, 6, and 10 in the first column of the figures consist of an outer loop), the classification accuracy clearly increases and the label precision of the extracted confident examples clearly increases (although the number of extracted confident examples decreases slightly). This implies that compared with previous classifiers and extracted confident examples, better ones are obtained, which empirically justifies the positive cycle. Note that the classification accuracy in the outer loop is low because the models are re-initialized.
Figure 3 also shows the importance of the outer loop of Me-Momentum. We can see that the label precision of the extracted confident examples slightly decreases in the inner loops. This is because the deep model gradually memorizes the noisy labels as we continually refine it. This issue can be handled by re-initialize the deep model in the outer loop. Specifically, we can see from Figure 3 that by re-initializing the model in the outer loop, the label precision of the extracted confident examples increases significantly. Although the number of the extracted confident examples decreases, the overall quality of the extracted confident examples is increasing as evidenced by the increase of the classification accuracy of the classifiers trained on the extracted confident data. Note that the low data quality in the first run of the inner loop also justifies that a single deep model initialization may lead to sample selection bias.
There are interesting observations of the proposed method that the number of extracted confident examples is close to the number of accurately labeled data in the training set and that the label precision of the extracted confident examples is quite high, i.e., almost all are above 90%. This empirically proves that Me-Momentum is powerful in extracting confident examples. In the next subsection, we will visualize that Me-Momentum is also good at extracting hard confident examples.

heading: 3.2 VISUALIZE HARD CONFIDENT EXAMPLES

text:
To justify that Me-Momentum is able to extract hard confident examples, we visualize the extracted confident examples by employing t-SNE (Maaten & Hinton, 2008). Specifically, we show how the
confident examples are progressively extracted in the inner and outer loops. The results are shown in Figure 4, where green, blue, and red dots represent confident examples extracted at the beginning, middle, and end rounds of the loops, respectively. On the datasets of MNIST and CIFAR10, we can clearly see that the blue and red dots are mostly located at the boundaries of the clusters of green dots. Although the figures of CIFAR100 are small, we can also clearly see that there are lots of blue and red dots which are outside of the green clusters in the second and fourth figures. This supports and justifies our claim that Me-Momentum is able to extract hard confident examples (those are close to the decision boundary).
Comparing the extracted results of the first run of the inner loop (the first and third columns) with those of the outer loop (the second and fourth columns), we can find that the cluster boundaries in the latter are more clear. This further justifies that why better classification performance can be obtained by re-initialization in the outer loop. Comparing the confident examples extracted on the class-dependent label noise datasets with those on the instance-dependent label noise datasets, we can see that the proposed method is not very sensitive to the type of label noise and can work well on the most general instance-dependent label noise cases.

heading: 3.3 CLASSIFICATION ACCURACY

text:
Synthetic data To evaluate the classification performance of Me-Momentum, we first conduct experiments on MNIST, CIFAR10, and CIFAR100 with class-dependent and instance-dependent label noise. Each trial is repeated five times. The results are presented in Tables 1, 2, and 3, respectively. Me-Momentum consistently outperforms the baselines. Specifically, CIFAR100 is the most challenging one among the three datasets. On CIFAR100, Me-Momentum outperforms the baselines by a clear margin across all the settings as shown in Table 3. Note that the performance gain in Me-Momentum is caused by the improvement of the quality of the extracted confident examples.
In the baselines, Co-teaching, Joint Optim, and T-revision are the representative methods that learn robust classifiers by extracting confident examples, refining the noisy labels, and exploiting the noise transition matrix, respectively. Note that Co-teaching keeps updating a constant number of confident
examples from the mini-batches used in SGD. We therefore do not compare with its extracted confident examples in Section 3.2 as our method extracts confident examples from the whole training data at once. By comparing the classification performance, we can clearly see that the proposed method is much more powerful in extracting confident examples. Note that Joint Optim and Trevision employ all training data to train the classifiers; while our method only employs confident examples and discards the unconfident ones. The results further justify that Me-Momentum is able to extract high-quality confident examples. Note that the performance of Me-Momentum could be further improved by correcting the unconfident data with the idea of Joint Optim.
Real-world dataset We compare Me-Momentum with baseline methods on Clothing1M in Table 4, where "pre-trained" and "scratch" mean the network was pre-trained by employing ImageNet and initialized randomly, respectively; "clean" and "noisy" means the validation data is clean and noisy respectively. First, it is observed that Me-Momentum works well with noisy validation, even surpassing many baselines with clean validation. For a fair comparison, we also use clean data to validate our method, which achieves the highest test accuracy of 75.18%, better than T-revision by 1% and Joint Optim by 2.95%. Note that Forward and T-revision need the 50k clean data for estimating transition matrix, while Me-Momentum does not need any clean
data for training. In addition, to show the robustness of Me-Momentum, we conduct experiments with ResNet-50 from scratch, which achieves the second best accuracy.

heading: 4 CONCLUSION

text: In this paper, we propose a method called Me-Momentum that is able to extract hard confident examples from noisily labeled data by exploiting the memorization effect of deep neural networks. In a high level, it fulfils a positive cycle that better confident examples will result in a better classifier and that a better classifier will identify better confident examples. We have empirically verified its effectiveness by analyzing the statistics of the extracted examples, visualizing the hard confident examples, and comparing its classification performance with state-of-the-art baselines. In future, we can extend our work by utilizing and exploiting the unconfident examples.

heading: A EARLY STOPPING

text:
We discuss the early stopping trick used in Step 1 of Algorithm 1. We repeat explaining the trick here again. Specifically, we introduce a definition of high-peak. A noisy validation accuracy at the ith epoch is called an i-th high-peak if it achieves the highest accuracy in the epoch range {1, . . . , i}. Assume the i-th and j-th high-peaks occur next to each other, having noisy validation accuracies of a and b, respectively. The training early stops if (b− a)/(j − i) ≤ τ , where τ is a hyper-parameter. In the experiments, we set τ = 0.1, which empirically works well across all datasets. In Figure 5, we compare the difference between the early stopping method and the traditional validation method.
We also study the sensitivity of the hyper-parameter. Specifically, we study its sensitivity on CIFAR10 by setting τ to be the values in the range {0.05, 0.07, 0.1, 0.3, 0.5}. Other settings are the same as those in this paper. The results are presented in Figure 6. We can see that the classification performance of Me-Momentum is robust and not sensitive to the change of the value of τ .

heading: B GENERATING LABEL NOISE

text:
Transition matrix The transition matrix T (x) was proposed to explicitly model the generation process of label noise, where Tij(x) = Pr(Ȳ = j|Y = i,X = x), Pr(A) denotes as the probability of the event A, X as the random variable for the instance, Ȳ as the noisy label, and Y as the latent clean label. In high level, the ij-th entry of the transition matrix denote the probability that the instance will flip from the clean class j to the noisy class i.
Symmetric class-dependent label noise The label noise is generated according to symmetric classdependent and instance-independent noise transition matrices. If the flip rate is α, the diagonal entries of a symmetric transition matrix are 1− α and the off-diagonal entries are α/(c− 1).
Instance-dependent label noise We generate the instance-dependent label noise according to the following Algorithm 2 Xia et al. (2020). More details about this algorithm can be found in Xia et al. (2020).
Algorithm 2 Instance-dependent Label Noise Generation Input: Clean samples {(xi, yi)}ni=1; Noise rate τ . 1: Sample instance flip rates q ∈ Rn from the truncated normal distribution τN (τ, 0.12, [0, 1]); 2: Independently sample w1, w2, . . . , wc from the standard normal distribution N (0, 12); 3: For i = 1, 2, . . . , n do 4: p = xi × wyi ; // generate instance-dependent flip rates 5: pyi = −∞; // control the diagonal entry of the instance-dependent transition matrix 6: p = qi × softmax(p); // make the sum of the off-diagonal entries of the yi-th row to be qi 7: pyi = 1− qi; // set the diagonal entry to be 1− qi 8: Randomly choose a label from the label space according to possibilities p as noisy label ȳi; 9: End for. Output: Noisy samples {(xi, ȳi)}ni=1

heading: C COMPARE RESULTS WITH SELF

text:
The performance of our re-implemented SELF (Tarvainen & Valpola, 2017) is not as good as that in the original paper. For a fair comparison, we change our backbone consistently with SELF and compare with the results from the original paper directly (without Mean Teacher (Tarvainen & Valpola, 2017)). Specifically, the network is changed to ResNet26 with Shake-shake regularization (Gastaldi, 2017) and the learning rate is changed to 0.05 and weight decay to 2e-4.
Table 5 shows that Me-Momentum outperforms SELF by a large margin in CIFAR10 and CIFAR100 with Symmetric 40% and Symmetric 60% noise. The gap between the performance of Me-Momentum and SELF becomes larger in Symmetric 60% in both datasets compared with Symmetric 40% because hard confident examples play a more important role in more noisy datasets. Specifically, both of the methods are based on the same backbone with Cross-Entropy loss, so the improvement of Me-Momentum can only be as a result of the quality of extracted confident examples. Therefore, Me-Momentum is able to extract better hard confident examples than SELF.
Furthermore, results in Table 5 shows that the performance of Me-Momentum can be improved by changing a better backbone. However, to show the effectiveness of the proposed method and avoid complexity, we simply choose in the paper the standard CNN network.

heading: D EXPERIMENTS COMPLEMENTARY TO SECTION 3.1

text: In Section 3.1, we discuss the statistics of the extracted confident examples. However, due the space limit, in the paper, we only provide parts of the empirical results. In this supplementary material, we provide the statistics on all the employed datasets and settings.

heading: E EXPERIMENTS COMPLEMENTARY TO SECTION 3.2

text:
In Section 3.2, we have visualize the extracted confident examples by using t-SNE. It verifies that the proposed Me-Momentum is effective to extract hard confident examples. However, due the space limit, in the paper, we only provide parts of the empirical results. In this supplementary material, we provide the visualization on all the employed datasets and settings.
Specifically, we show how the confident examples are progressively extracted in the inner and outer loops. In the figures, green, blue, and red dots represent confident examples extracted at the beginning, middle, and end rounds of the loops, respectively.
On the datasets of MNIST and CIFAR10, we can clearly see that the blue and red dots are mostly located at the boundaries of the clusters of green dots. On CIFAR100, we can also clearly see that
there are lots of blue and red dots which are outside of the green clusters in the second and fourth figures. This supports and justifies our claim that Me-Momentum is able to extract hard confident examples (those are close to the decision boundary).
The figures are presented in the next and the following pages.


summaries: First, the paper identifies k-Nearest Neighbor (kNN) and radius Nearest Neighbor (rNN) to be naturally effective baseline certified defenses against data poisoning attack. It is easy to see that kNN and rNN are resistant to poison attacks, since to flip the prediction of a test example, one would need to insert/delete enough examples to change the majority vote. Second, the paper proposes a joint certificate that further improves certified accuracy for rNN. Specifically, it uses the fact that for any given poison removal budget, it can only decrease the vote for a single label. Even though the idea is simple, the experimental result is quite impressive significantly outperforming the previous more sophisticated certified defense methods.

summaries: The paper studies robustness of k-NN and r-NN against data poisoning attacks. The main message of the paper is that k-NN and r-NN are automatically resilient against attacks. Furthermore, by grouping test examples based their predicted labels. Data points with different predictions are grouped together, and then better certification guarantee can be derived. Experimental results demonstrate that k-NN and r-NN are indeed self-robust against data poisoning attacks.

summaries: This paper studies to train a certifiable robust model against data poisoning attacks using nearest neighbors. The paper studies the voting mechanism in the nearest neighbor models, and presents a relationship between the poisoning instances and the difference between the majority votes and the second majority votes. Such a relationship will result in a guarantee on the lower bound of a training model's accuracy, which is referred to as Certified Accuracy (CA). The theoretical results are neat. The experiments are conducted on MNIST and CIFAR, and results show better CA than previous approaches of DPA and Bagging.

abstractText: Data poisoning attacks aim to corrupt a machine learning model via modifying, adding, and/or removing some carefully selected training examples, such that the corrupted model predicts any or attacker-chosen incorrect labels for testing examples. The key idea of state-of-the-art certified defenses against data poisoning attacks is to create a majority vote mechanism to predict the label of a testing example. Moreover, each voter is a base classifier trained on a subset of the training dataset. Nearest neighbor algorithms such as k nearest neighbors (kNN) and radius nearest neighbors (rNN) have intrinsic majority vote mechanisms. In this work, we show that the intrinsic majority vote mechanisms in kNN and rNN already provide certified robustness guarantees against general data poisoning attacks. Moreover, our empirical evaluation results on MNIST and CIFAR10 show that the intrinsic certified robustness guarantees of kNN and rNN outperform those provided by state-of-the-art certified defenses.

authors:
Laurent Amsaleg
James Bailey
Dominique Barbe
Sarah Erfani
Michael E Houle
Vinh Nguyen
Miloš Radovanović

title: The vulnerability of learning to adversarial perturbation increases with intrinsic dimensionality

venue: IEEE Workshop on Information Forensics and Security (WIFS),

authors:
Dara Bahri
Heinrich Jiang
Maya Gupta

title: Deep k-nn for noisy labels

authors:
Marco Barreno
Blaine Nelson
Russell Sears
Anthony D Joseph
J Doug Tygar

title: Can machine learning be secure

venue: In Proceedings of the 2006 ACM Symposium on Information, computer and communications security,

authors:
Marco Barreno
Blaine Nelson
Anthony D Joseph
J Doug Tygar

title: The security of machine learning

authors:
Battista Biggio
Igino Corona
Giorgio Fumera
Giorgio Giacinto
Fabio Roli

title: Bagging classifiers for fighting poisoning attacks in adversarial classification tasks

venue: In International workshop on multiple classifier systems,

authors:
Battista Biggio
B Nelson
P Laskov

title: Poisoning attacks against support vector machines

authors:
Battista Biggio
Giorgio Fumera
Fabio Roli

title: Security evaluation of pattern classifiers under attack

venue: IEEE transactions on knowledge and data engineering,

authors:
Battista Biggio
Ignazio Pillai
Samuel Rota Bulò
Davide Ariu
Marcello Pelillo
Fabio Roli

title: Is data clustering in adversarial settings secure

venue: In Proceedings of the 2013 ACM workshop on Artificial intelligence and security,

authors:
Battista Biggio
Konrad Rieck
Davide Ariu
Christian Wressnegger
Igino Corona
Giorgio Giacinto
Fabio Roli

title: Poisoning behavioral malware clustering

venue: In Proceedings of the 2014 workshop on artificial intelligent and security workshop,

authors:
Nicholas Carlini
David Wagner

title: Towards evaluating the robustness of neural networks

venue: In IEEE S&P,

authors:
Xinyun Chen
Chang Liu
Bo Li
Kimberly Lu
Dawn Song

title: Targeted backdoor attacks on deep learning systems using data poisoning

venue: arXiv preprint arXiv:1712.05526,

authors:
Gilad Cohen
Guillermo Sapiro
Raja Giryes

title: Detecting adversarial samples using influence functions and nearest neighbors

venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,

authors:
Thomas Cover
Peter Hart

title: Nearest neighbor pattern classification

venue: IEEE transactions on information theory,

authors:
Gabriela F Cretu
Angelos Stavrou
Michael E Locasto
Salvatore J Stolfo
Angelos D Keromytis

title: Casting out demons: Sanitizing training data for anomaly sensors

venue: IEEE Symposium on Security and Privacy,

authors:
Navneet Dalal
Bill Triggs

title: Histograms of oriented gradients for human detection

venue: IEEE computer society conference on computer vision and pattern recognition (CVPR’05),

authors:
Ambra Demontis
Marco Melis
Maura Pintor
Matthew Jagielski
Battista Biggio
Alina Oprea
Cristina Nita-Rotaru
Fabio Roli

title: Why do adversarial attacks transfer? explaining transferability of evasion and poisoning attacks

venue: In USENIX Security Symposium,

authors:
Abhimanyu Dubey
Laurens van der Maaten
Zeki Yalniz
Yixuan Li
Dhruv Mahajan

title: Defense against adversarial images using web-scale nearest-neighbor search

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Jiashi Feng
Huan Xu
Shie Mannor
Shuicheng Yan

title: Robust logistic regression and classification

venue: In Advances in neural information processing systems,

authors:
Evelyn Fix
JL Hodges

title: Discriminatory analysis: Nonparametric discrimination, consistency properties

venue: Report No. 4, USAF School of Aviation

authors:
Wei Gao
Xin-Yi Niu
Zhi-Hua Zhou

title: On the consistency of exact and approximate nearest neighbor with noisy data

authors:
Ian J Goodfellow
Jonathon Shlens
Christian Szegedy

title: Explaining and harnessing adversarial examples

venue: arXiv preprint arXiv:1412.6572,

authors:
Tianyu Gu
Brendan Dolan-Gavitt
Siddharth Garg

title: Badnets: Identifying vulnerabilities in the machine learning model supply chain

venue: arXiv preprint arXiv:1708.06733,

authors:
Isabelle Guyon
Nada Matic
Vladimir Vapnik

title: Discovering informative patterns and data cleaning

venue: In Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining,

authors:
W Ronny Huang
Jonas Geiping
Liam Fowl
Gavin Taylor
Tom Goldstein

title: Metapoison: Practical general-purpose clean-label data poisoning

venue: arXiv preprint arXiv:2004.00225,

authors:
Matthew Jagielski
Alina Oprea
Battista Biggio
Chang Liu
Cristina Nita-Rotaru
Bo Li

title: Manipulating machine learning: Poisoning attacks and countermeasures for regression learning

venue: IEEE Symposium on Security and Privacy (SP),

authors:
Jinyuan Jia
Xiaoyu Cao
Neil Zhenqiang Gong

title: Intrinsic certified robustness of bagging against data poisoning attacks

venue: arXiv preprint arXiv:2008.04495,

authors:
Alexander Levine
Soheil Feizi

title: Deep partition aggregation: Provable defense against general poisoning

venue: attacks. arXiv preprint arXiv:2006.14768,

authors:
Bo Li
Yining Wang
Aarti Singh
Yevgeniy Vorobeychik

title: Data poisoning attacks on factorizationbased collaborative filtering

authors:
Yuzhe Ma
Xiaojin Zhu
Justin Hsu

title: Data poisoning against differentially-private learners: Attacks and defenses

venue: In International Joint Conference on Artificial Intelligence,

authors:
Shike Mei
Xiaojin Zhu

title: The security of latent dirichlet allocation

venue: In Artificial Intelligence and Statistics,

title: Using machine teaching to identify optimal training-set attacks on machine learners

venue: In AAAI,

authors:
Mehran Mozaffari-Kermani
Susmita Sur-Kolay
Anand Raghunathan
Niraj K Jha

title: Systematic poisoning attacks on and defenses for machine learning in healthcare

venue: IEEE journal of biomedical and health informatics,

authors:
Luis Muñoz-González
Battista Biggio
Ambra Demontis
Andrea Paudice
Vasin Wongrassamee
Emil C Lupu
Fabio Roli

title: Towards poisoning of deep learning algorithms with back-gradient optimization

venue: In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security,

authors:
Blaine Nelson
Marco Barreno
Fuching Jack Chi
Anthony D Joseph
Benjamin IP Rubinstein
Udam Saini
Charles A Sutton
J Doug Tygar
Kai Xia

title: Exploiting machine learning to subvert your spam

venue: filter. LEET,

authors:
Nicolas Papernot
Patrick McDaniel

title: Deep k-nearest neighbors: Towards confident, interpretable and robust deep learning

venue: arXiv preprint arXiv:1803.04765,

authors:
Neehar Peri
Neal Gupta
W Ronny Huang
Liam Fowl
Chen Zhu
Soheil Feizi
Tom Goldstein
John P Dickerson

title: Deep k-nn defense against clean-label data poisoning

authors:
Henry WJ Reeve
Ata Kabán

title: Fast rates for a knn classifier robust to unknown asymmetric label noise

authors:
Elan Rosenfeld
Ezra Winston
Pradeep Ravikumar
J Zico Kolter

title: Certified robustness to label-flipping attacks via randomized smoothing

authors:
Benjamin IP Rubinstein
Blaine Nelson
Ling Huang
Anthony D Joseph
Shing-hon Lau
Satish Rao
Nina Taft
J Doug Tygar

title: Antidote: understanding and defending against poisoning of anomaly detectors

venue: In Proceedings of the 9th ACM SIGCOMM conference on Internet measurement,

authors:
Ali Shafahi
W Ronny Huang
Mahyar Najibi
Octavian Suciu
Christoph Studer
Tudor Dumitras
Tom Goldstein

title: Poison frogs! targeted clean-label poisoning attacks on neural networks

authors:
Chawin Sitawarin
David Wagner

title: Defending against adversarial examples with k-nearest neighbor

venue: arXiv preprint arXiv:1906.09525,

title: On the robustness of deep k-nearest neighbors

venue: IEEE Security and Privacy Workshops (SPW),

authors:
Jacob Steinhardt
Pang Wei W Koh
Percy S Liang

title: Certified defenses for data poisoning attacks

authors:
Octavian Suciu
Radu Marginean
Yigitcan Kaya
Hal Daume III
Tudor Dumitras

title: When does machine learning FAIL? generalized transferability for evasion and poisoning attacks

authors:
Christian Szegedy
Wojciech Zaremba
Ilya Sutskever
Joan Bruna
Dumitru Erhan
Ian Goodfellow
Rob Fergus

title: Intriguing properties of neural networks

authors:
Brandon Tran
Jerry Li
Aleksander Madry

title: Spectral signatures in backdoor attacks

venue: In Advances in Neural Information Processing Systems,

authors:
Jeroen Vuurens
Arjen P de Vries
Carsten Eickhoff

title: How much spam can you take? an analysis of crowdsourcing results to increase accuracy

venue: In Proc. ACM SIGIR Workshop on Crowdsourcing for Information Retrieval

authors:
Lu Wang
Xuanqing Liu
Jinfeng Yi
Zhi-Hua Zhou
Cho-Jui Hsieh

title: Evaluating the robustness of nearest neighbor classifiers: A primal-dual perspective

authors:
Yizhen Wang
Somesh Jha
Kamalika Chaudhuri

title: Analyzing the robustness of nearest neighbors to adversarial examples

venue: In International Conference on Machine Learning,

title: Asymptotic properties of nearest neighbor rules using edited data

venue: IEEE Transactions on Systems, Man, and Cybernetics,

authors:
Huang Xiao
Battista Biggio
Gavin Brown
Giorgio Fumera
Claudia Eckert
Fabio Roli

title: Is feature selection secure against training data poisoning

authors:
Huang Xiao
Battista Biggio
Blaine Nelson
Han Xiao
Claudia Eckert
Fabio Roli

title: Support vector machines under adversarial label contamination

authors:
Yao-Yuan Yang
Cyrus Rashtchian
Yizhen Wang
Kamalika Chaudhuri

title: Robustness for nonparametric classification: A generic attack and defense

venue: In International Conference on Artificial Intelligence and Statistics,

authors:
Chen Zhu
W Ronny Huang
Hengduo Li
Gavin Taylor
Christoph Studer
Tom Goldstein

title: Transferable clean-label poisoning attacks on deep neural nets

heading: 1 INTRODUCTION

text:
Data poisoning attacks (Barreno et al., 2006; Nelson et al., 2008; Biggio et al., 2012; 2013a; Xiao et al., 2015b; Steinhardt et al., 2017; Shafahi et al., 2018) aim to corrupt the training phase of a machine learning system via carefully poisoning its training dataset including modifying, adding, and/or removing some training examples. The corrupted model predicts incorrect labels for testing examples. Data poisoning attacks pose severe security concerns to machine learning in critical application domains such as autonomous driving (Gu et al., 2017), cybersecurity (Rubinstein et al., 2009; Suciu et al., 2018; Chen et al., 2017), and healthcare analytics (Mozaffari-Kermani et al., 2014). Unlike adversarial examples (Szegedy et al., 2014; Goodfellow et al., 2014; Carlini & Wagner, 2017), which add perturbation to each testing example to induce misclassification, data poisoning attacks corrupt the model such that it misclassifies many clean testing examples.
Multiple certifiably robust learning algorithms (Ma et al., 2019; Rosenfeld et al., 2020; Levine & Feizi, 2020; Jia et al., 2020) against data poisoning attacks were recently developed. A learning algorithm is certifiably robust against data poisoning attacks if it can learn a classifier on a training dataset that achieves a certified accuracy on a testing dataset when the number of poisoned training examples is no more than a threshold (called poisoning size). The certified accuracy of a learning algorithm is a lower bound of the accuracy of its learnt classifier no matter how an attacker poisons the training examples with the given poisoning size. The key idea of state-of-the-art certifiably robust learning algorithms (Levine & Feizi, 2020; Jia et al., 2020) is to create a majority vote mechanism to predict the label of a testing example. In particular, each voter votes a label for a testing example and the final predicted label is the majority vote among multiple voters. For instance, Deep Partition Aggregation (DPA) (Levine & Feizi, 2020) divides the training dataset into disjoint partitions and learns a base classifier (i.e., a voter) on each partition. Bagging (Jia et al., 2020) also learns multiple base classifiers (i.e., voters), but each of them is learnt on a random subsample of the training dataset. We denote by a and b the labels with the largest and second largest number of votes, respectively. Moreover, sa and sb respectively are the number of votes for labels a and b when there are no corrupted voters. The corrupted voters change their votes from a to b in the worst-case scenario. Therefore, the majority vote result (i.e., the predicted label for a testing example) remains to be a when the number of corrupted voters is no larger than d sa−sb2 e − 1. In other words, the number of corrupted voters that a majority vote mechanism can tolerate depends on the gap sa − sb between the largest and the second largest number of votes.
However, state-of-the-art certifiably robust learning algorithms achieve suboptimal certified accuracies due to two key limitations. First, each poisoned training example leads to multiple corrupted voters in the worse-case scenarios. In particular, modifying a training example corrupts two voters (i.e., two base classifiers) in DPA (Levine & Feizi, 2020) and corrupts the voters whose training subsamples include the modified training example in bagging (Jia et al., 2020). Therefore, given the same gap sa − sb between the largest and the second largest number of votes, the majority vote result is robust against a small number of poisoned training examples. Second, they can only certify robustness for each testing example individually because it is hard to quantify how poisoned training examples corrupt the voters for different testing examples jointly. Suppose the classifier learnt by a learning algorithm can correctly classify testing inputs x1 and x2. An attacker can poison e training examples such that the learnt classifier misclassifies x1 or x2, but the attacker cannot poison e training examples such that both x1 and x2 are misclassified. When the poisoning size is e, existing certifiably robust learning algorithms would produce a certified accuracy of 0 for the two testing examples. However, the certified accuracy can be 1/2 if we consider them jointly.
k nearest neighbors (kNN) and radius nearest neighbors (rNN) (Fix & Hodges, 1951; Cover & Hart, 1967) have intrinsic majority vote mechanisms. Specifically, given a testing example, kNN (or rNN) predicts its label via taking a majority vote among the labels of its k nearest neighbors (or neighbors within radius r) in the training dataset. Our major contribution in this work is that we show the intrinsic majority vote mechanisms in kNN and rNN make them certifiably robust against data poisoning attacks. Moreover, kNN and rNN address the limitations of state-of-the-art certifiably robust learning algorithms. Specifically, each poisoned training example leads to only one corrupted voter in the worse-case scenario in kNN and rNN. Therefore, given the same gap sa− sb, the majority vote result (i.e., predicted label for a testing example) is robust against more poisoned training examples in kNN and rNN. Furthermore, we show that rNN enables joint certification of multiple testing examples. Figure 1 illustrates an example of individual certification and joint certification with two testing examples in rNN. When we treat the two testing examples individually, an attacker can poison 3 training examples such that rNN misclassifies each of them. However, when we treat them jointly, an attacker cannot poison 3 training examples to misclassify both of them. We propose such joint certification to derive a better certified accuracy for rNN. Specifically, we design methods to group testing examples in a testing dataset such that we can perform joint certification for each group of testing examples.
We evaluate our methods on MNIST and CIFAR10 datasets. We use `1 distance metric to calculate nearest neighbors. First, our methods substantially outperform state-of-the-art certifiably robust learning algorithms. For instance, when an attacker can arbitrarily poison 1,000 training examples on MNIST, the certified accuracy of rNN with r = 4 is 40.8% and 33.5% higher than those of DPA (Levine & Feizi, 2020) and bagging (Jia et al., 2020), respectively. Second, our joint certification improves certified accuracy. For instance, our joint certification improves the certified accuracy of rNN by 15.1% when an attacker can arbitrarily poison 1,000 training examples on MNIST.
In summary, we make the following contributions:
• We derive the intrinsic certified robustness guarantees of kNN and rNN against data poisoning attacks.
• We propose joint certification of multiple testing examples to derive a better certified robustness guarantee for rNN. rNN is the first method that supports joint certification of multiple testing examples against data poisoning attacks.
• We evaluate our methods and compare them with state-of-the-art on MNIST and CIFAR10.

heading: 2 PROBLEM SETUP

text:
Learning setting: Assuming we have a training dataset Dtr with n training examples. We denote by M a learning algorithm. Moreover, we denote byM(Dtr,x) the label predicted for a testing input x by a classifier learnt byM on the training dataset Dtr. For instance, given a training dataset Dtr and a testing input x, kNN finds the k training examples in Dtr that are the closest to x as the nearest neighbors, while rNN finds the training examples in Dtr whose distances to x are no larger than r as the nearest neighbors. The distance between a training input and a testing input can be measured by any distance metric. Then, kNN and rNN use majority vote among the nearest neighbors to predict the label of x. Specifically, each nearest neighbor is a voter and votes its label for the testing input x; and the label with the largest number of votes is the final predicted label for x.
Data poisoning attacks: We consider data poisoning attacks (Rubinstein et al., 2009; Biggio et al., 2012; Xiao et al., 2015a; Li et al., 2016; Muñoz-González et al., 2017; Jagielski et al., 2018) that aim to poison (i.e., modify, add, and/or remove) some carefully selected training examples in Dtr such that the corrupted classifier has a low accuracy for testing examples indiscriminately. For simplicity, we use D∗tr to denote the poisoned training dataset. Moreover, we define the poisoning size e as the minimal number of modified/added/removed training examples that can turn Dtr into D∗tr. We use S(Dtr, e) to denote the set of poisoned training datasets whose poisoning sizes are at most e. Formally, we define S(Dtr, e) as follows:
S(Dtr, e) = {D∗tr|max{|D∗tr|, |Dtr|} − |D∗tr ∩Dtr| ≤ e}, (1)
where max{|D∗tr|, |Dtr|} − |D∗tr ∩Dtr| is the poisoning size of D∗tr. Note that modifying a training example is equivalent to removing a training example and adding a new one. Given a training dataset Dtr and a poisoning size e, an attacker aims to craft a poisoned training dataset D∗tr to minimize the testing accuracy of the classifier learnt by algorithmM on D∗tr.
Certified accuracy: Given a training dataset Dtr and a learning algorithmM, we use certified accuracy on a testing dataset Dte = {(xi, yi)}ti=1 to measure the algorithm’s performance. Specifically, we denote certified accuracy at poisoning size e as CA(e) and formally define it as follows:
CA(e) = min D∗tr∈S(Dtr,e)
∑ (xi,yi)∈Dte I(M(D ∗ tr,xi) = yi)
|Dte| , (2)
where I is the indicator function andM(D∗tr,xi) is the label predicted for a testing input xi by the classifier learnt by the algorithmM on the poisoned training dataset D∗tr. CA(e) is the least testing accuracy on Dte that the learning algorithmM can achieve no matter how an attacker poisons the training examples when the poisoning size is at most e. Our goal is to derive lower bounds of CA(e) for learning algorithms kNN and rNN.

heading: 3 CERTIFIED ACCURACY OF KNN AND RNN

text: We first derive a lower bound of the certified accuracy via individual certification, which treats testing examples in Dte individually. Then, we derive a better lower bound of the certified accuracy for rNN via joint certification, which treats testing examples jointly.

heading: 3.1 INDIVIDUAL CERTIFICATION

text:
Given a poisoning size at most e, our idea is to certify whether the predicted label stays unchanged or not for each testing input individually. If the predicted label of a testing input x stays unchanged
(i.e.,M(Dtr,x) =M(D∗tr,x)) and it matches with the testing input’s true label, then kNN or rNN certifiably correctly classifies the testing input when the poisoning size is at most e. Therefore, we can obtain a lower bound of the certified accuracy at poisoning size e as the fraction of testing inputs in Dte which kNN or rNN certifiably correctly classifies. Next, we first discuss how to certify whether the predicted label stays unchanged or not for each testing input individually. Then, we show our lower bound of the certified accuracy at poisoning size e.
Certifying the predicted label of a testing input: Our goal is to certify that M(Dtr,x) = M(D∗tr,x) for a testing input x when the poisoning size is no larger than a threshold. Given a training dataset Dtr (or a poisoned training dataset D∗tr) and a testing input x, we use N (Dtr,x) (or N (D∗tr,x)) to denote the set of nearest neighbors of x in Dtr (or D∗tr) for kNN or rNN. We note that there may exist ties when determining the nearest neighbors for kNN, i.e., multiple training examples may have the same distance to the testing input. Usually, kNN breaks such ties uniformly at random. However, such random ties breaking method introduces randomness, i.e., the difference of nearest neighbors before and after poisoned training examples (i.e., N (Dtr,x) vs. N (D∗tr,x)) depends on the randomness in breaking ties. Such randomness makes it challenging to certify the robustness of the predicted label against poisoned training examples. To address the challenge, we propose to define a deterministic ranking of training examples and break ties via choosing the training examples with larger ranks. Moreover, such ranking between clean training examples does not depend on poisoned ones. For instance, we can use a cryptographic hash function (e.g., SHA-1) that is very unlikely to have collisions to hash each training example based on its input feature vector and label, and then we rank the training examples based on their hash values.
We use sl to denote the number of votes in N (Dtr,x) for label l, i.e., the number of nearest neighbors in N (Dtr,x) whose labels are l. Formally, we have sl = ∑ (xj ,yj)∈N (Dtr,x) I(yj = l), where l = 1, 2, · · · , c and I is an indicator function. kNN or rNN essentially predicts the label of the testing input x as the label with the largest number of votes, i.e.,M(Dtr,x) = argmaxl∈{1,2,··· ,c} sl. Suppose a and b are the labels with the largest and second largest number of votes, i.e., sa and sb are the largest and second largest ones among {s1, s2, · · · , sc}, respectively. We note that there may exist ties when comparing the labels based on their votes. We define a deterministic ranking of labels in {1, 2, · · · , c} and take the label with the largest rank when such ties happen. In the worse-case scenario, each poisoned training example leads to one corrupted voter in kNN or rNN, which changes its vote from label a to label b. Therefore, kNN or rNN still predicts label a for the testing input x when the number of poisoned training examples is no more than d sa−sb2 e − 1 (without considering the ties breaking). Formally, we have the following theorem: Theorem 1. Assuming we have a training dataset Dtr, a testing input x, and a nearest neighbor algorithmM (i.e., kNN or rNN). a and b respectively are the two labels with the largest and second largest number of votes among the nearest neighbors N (Dtr,x) of x in Dtr. Moreover, sa and sb are the number of votes for a and b, respectively. Then, we have the following:
M(D∗tr,x) = a,∀D∗tr ∈ S(Dtr, e), e ≤ d sa − sb + I(a > b)
2 e − 1. (3)
Proof. When an attacker poisons at most e training examples, the number of changed nearest neighbors in N (Dtr,x) is at most e. We denote by s∗l = ∑ (xj ,yj)∈N (D∗tr,x)
I(l = yj) the number of votes for label l among the nearest neighbors N (D∗tr,x) in the poisoned training dataset, where l = 1, 2, · · · , c. Then, we have sl − e ≤ s∗l ≤ sl + e for each l = 1, 2, · · · , c. Therefore, when e ≤ d sa−sb+I(a>b)2 e−1, we have s ∗ a−s∗b ≥ sa−sb−2·e > 0 if a < b and s∗a−s∗b ≥ sa−sb−2·e ≥ 0 if a > b. Thus, the nearest neighbor algorithm still predicts label a for x in both cases based on our way of breaking ties, i.e., we haveM(D∗tr,x) = a when e ≤ d sa−sb+I(a>b) 2 e − 1.
Deriving a lower bound of CA(e): kNN or rNN certifiably correctly classifies a testing input x if it correctly predicts its label before attacks and the predicted label stays unchanged after an attacker poisons the training dataset. Therefore, the fraction of testing inputs that kNN or rNN certifiably correctly classifies is a lower bound of CA(e). Formally, we have the following theorem: Theorem 2 (Individual Certification). Assuming we have a training dataset Dtr, a testing dataset Dte = {(xi, yi)}ti=1, and a nearest neighbor algorithmM (i.e., kNN or rNN). ai and bi respectively are the two labels with the largest and second largest number of votes among the nearest neighbors
N (Dtr,xi) of xi in Dtr. Moreover, sai and sbi are the number of votes for ai and bi, respectively. Then, we have the following lower bound of CA(e):
CA(e) ≥ ∑ (xi,yi)∈Dte I(ai = yi) · I(e ≤ e ∗ i )
|Dte| , (4)
where e∗i = d sai−sbi+I(ai>bi) 2 e − 1.
Proof. See Appendix A.

heading: 3.2 JOINT CERTIFICATION

text:
We derive a better lower bound of the certified accuracy via jointly considering multiple testing examples. Our intuition is that, given a group of testing examples and a poisoning size e, an attacker may not be able to make a learning algorithm misclassify all the testing examples jointly even if it can make the learning algorithm misclassify each of them individually. In particular, rNN enables such joint certification. It is challenging to perform joint certification for kNN because of the complex interactions between the nearest neighbors of different testing examples (see our proof of Theorem 3 for specific reasons). Next, we first derive a lower bound of CA(e) on a group of testing examples for rNN. Then, we derive a lower bound of CA(e) on the testing dataset Dte via dividing it into groups. Finally, we discuss different strategies to divide the testing dataset into groups, which may lead to different lower bounds of CA(e).
Deriving a lower bound of CA(e) for a group of testing examples: Suppose we have a group of testing examples which have different predicted labels in rNN. Our key intuition is that when an attacker can poison e training examples, the attacker can only decrease the total votes for the testing examples’ predicted labels by at most e in rNN, as the testing examples’ predicted labels are different. We denote by U a group of testing examples with different predicted labels and by m its size, i.e., m = |U|. The next theorem shows a lower bound of CA(e) on the testing examples in U for rNN. Theorem 3. Assuming we have a training dataset Dtr, the learning algorithm rNN, and a group of m testing examples U = {(xi, yi)}mi=1 with different predicted labels. ai and bi respectively are the two labels with the largest and second largest number of votes among the nearest neighbors N (Dtr,xi) of xi in Dtr. Moreover, sai and sbi are the number of votes for ai and bi, respectively. Without loss of generality, we assume the following:
(sa1 − sb1) · I(a1 = y1) ≥ (sa2 − sb2) · I(a2 = y2) ≥ · · · ≥ (sam − sbm) · I(am = ym). (5)
Then, the certified accuracy at poisoning size e of rNN for U has a lower bound CA(e) ≥ w−1|U| , where w is the solution to the following optimization problem:
w = argmin w′,w′≥1 w′ s.t. m∑ i=w′ max(sai − sbi − e+ I(ai > bi), 0) · I(ai = yi) ≤ e. (6)
Proof. When an attacker can poison at most e training examples, the attacker can add at most e new nearest neighbors and remove e existing ones in N (Dtr,xi) (equivalent to modifying e training examples) in the worst-case scenario. We denote by s∗ai and s ∗ bi
respectively the number of votes for labels ai and bi among the nearest neighbors N (D∗tr,xi). First, we have s∗bi ≤ sbi + e for ∀i ∈ {1, 2, · · · ,m} since at most e new nearest neighbors are added. Second, we have s∗ai ≥ sai−ei in rNN, where ei is the number of removed nearest neighbors in N (Dtr,xi) whose true labels are ai. Note that kNN does not support joint certification because s∗ai ≥ sai − ei does not hold for kNN. Next, we derive the minimal value of ei such that rNN misclassifies xi. In particular, we consider two cases. If ai 6= yi, i.e., xi is misclassified by rNN without attack, then we have ei = 0. If ai = yi, xi is misclassified by rNN when s∗ai ≤ s ∗ bi if ai < bi and s∗ai < s ∗ bi
if ai > bi after attack, which means ei ≥ sai − sbi − e + I(ai > bi). Since ei ≥ 0, we have ei ≥ max(sai − sbi − e + I(ai > bi), 0). Combining the two cases, we have the following lower bound for ei that makes rNN misclassify xi: ei ≥ max(sai − sbi − e+ I(ai > bi), 0) · I(ai = yi). Moreover, since the attacker can remove at most e training examples and the group of testing examples have different predicted labels, i.e., ai 6= aj ∀i, j ∈ {1, 2, · · · ,m} and i 6= j, we have ∑m i=1 ei ≤ e. We note that the lower bound of
ei is non-increasing as i increases based on Equation (5). Therefore, in the worst-case scenario, the attacker can make rNN misclassify the last m− w + 1 testing inputs whose corresponding ei sum to be at most e. Formally, w is the solution to the optimization problem in Equation (6). Therefore, the certified accuracy at poisoning size e is at least w−1|U| .
Deriving a lower bound of CA(e) for a testing dataset: Based on Theorem 3, we can derive a lower bound of CA(e) for a testing dataset via dividing it into disjoint groups, each of which includes testing examples with different predicted labels in rNN. Formally, we have the following theorem: Theorem 4 (Joint Certification). Given a testing dataset Dte, we divide it into λ disjoint groups, i.e., U1,U2, · · · ,Uλ, where the testing examples in each group have different predicted labels in rNN. Then, we have the following lower bound of CA(e):
CA(e) ≥ ∑λ j=1 µj · |Uj |∑λ j=1 |Uj | , (7)
where µj is the lower bound of the certified accuracy at poisoning size e on group Uj , which we can obtain by invoking Theorem 3.
Proof. See Appendix B.
Strategies of grouping testing examples: Our Theorem 4 is applicable to any way of dividing the testing examples in Dte to disjoint groups once the testing examples in each group have different predicted labels in rNN. Therefore, a natural question is how to group the testing examples in Dte to maximize our lower bound of certified accuracy. For instance, a naive method is to randomly divide the testing examples into disjoint groups, each of which includes at most c (the number of classes) testing examples with different predicted labels. We call such method Random Division (RD). However, RD achieves suboptimal performance because it does not consider the certified robustness of each individual testing example. In particular, some testing examples can or cannot be certifiably correctly classified no matter which groups they belong to. However, if we group them with other testing examples, the certified accuracy may be degraded because each group can have at most c testing examples. For instance, if a testing example cannot be certifiably correctly classified no matter which group it belongs to, then adding it to a group would exclude another testing example from the group, which may degrade the certified accuracy for the group.
Therefore, we propose to isolate these testing examples and divide the remaining testing examples into disjoint groups. We call such method Isolation and Division (ISLAND). Specifically, we first divide the testing dataset Dte into three disjoint parts which we denote as D0te, D 1 te, and D 2 te. D 0 te contains the testing examples that cannot be certifiably correctly classified at poisoning size e no matter which group they belong to. Based on our proof of Theorem 3, a testing example (xi, yi) that satisfies (sai − sbi − e + I(ai > bi)) · I(ai = yi) ≤ 0 cannot be certifiably correctly classified at poisoning size e no matter which group it belongs to. Therefore, D0te includes such testing examples. Moreover, based on Theorem 1, a testing example (xi, yi) that satisfies e ≤ d sai−sbi+I(ai>bi) 2 e − 1 can be certifiably correctly classified at poisoning size e. Therefore, D1te includes such testing examples. Each testing example in D0te or D 1 te forms a group by itself. D 2 te includes the remaining testing examples, which we further divide into groups. Our method of dividing D2te into groups is inspired by the proof of Theorem 3. In particular, we form a group of testing examples as follows: for each label l ∈ {1, 2, · · · , c}, we find the testing example that has the largest value of (sai − sbi − e+ I(ai > bi)) · I(ai = l) and we skip the label if there is no remaining testing example whose predicted label is l. We apply the procedure to recursively group the testing examples in D2te until no testing examples are left.

heading: 4 EVALUATION

text:
Datasets: We evaluate our methods on MNIST and CIFAR10. We use the popular histogram of oriented gradients (HOG)1 (Dalal & Triggs, 2005) method to extract features for each example, which
1Public implementation: https://scikit-image.org/docs/dev/api/skimage.feature.html#skimage.feature.hog
we found improves certified accuracy. Note that previous work (Jia et al., 2020) used a pre-trained model to extract features via transfer learning. However, the pre-trained model may also be poisoned and thus we don’t use it. We didn’t find ties in determining nearest neighbors for kNN in our experiments. We rank the labels as {1, 2, · · · , 10} to break ties for labels. Parameter settings: While any distance metric is applicable, we use `1 in our experiments for both kNN and rNN. Unless otherwise mentioned, we adopt the following settings: k = 5, 000 for both MNIST and CIFAR10 in kNN; and r = 4 for MNIST and r = 20 for CIFAR10 in rNN, considering the different feature dimensions of MNIST and CIFAR10. By default, we use the ISLAND grouping method in the joint certification for rNN.
Comparing with DPA (Levine & Feizi, 2020) and bagging (Jia et al., 2020): Figure 2a and Figure 2b show the comparison results of DPA, bagging, kNN, and rNN. DPA divides a training dataset into ζ disjoint partitions and learns a base classifier on each of them. Then, DPA takes a majority vote among the base classifiers to predict the label of a testing example. Bagging learns N base classifiers, each of which is learnt on a random subsample with ξ training examples of the training dataset. Moreover, bagging’s certified accuracy is correct with a confidence level 1− α. All the compared methods have tradeoffs between accuracy under no attacks (i.e., CA(0)) and robustness against attacks. Therefore, we set their parameters such that they have similar accuracy under no attacks (i.e., similar CA(0)). In particular, we use the default k for kNN, and we adjust r for rNN, ζ for DPA, and ξ for bagging. The searched parameters are as follows: r = 4, ζ = 5, 500, and ξ = 27 for MNIST; and r = 21, ζ = 900, and ξ = 400 for CIFAR10. Note that we set N = 1, 000 and α = 0.001 for bagging following (Jia et al., 2020).
We have the following observations. First, both kNN and rNN outperform DPA and bagging. The superior performance of kNN and rNN stems from two reasons: 1) each poisoned training example corrupts multiple voters for DPA and bagging, while it only corrupts one voter for kNN and rNN, which means that, given the same gap between the largest and second largest number of votes, kNN and rNN can tolerate more poisoned training examples; and 2) rNN enables joint certification that improves the certified accuracy. Second, rNN achieves better certified accuracy than kNN when the poisoning size is large. The reason is that rNN supports joint certification.
Comparing individual certification with joint certification: Figure 2c and Figure 2d compare individual certification and joint certification (with the RD and ISLAND grouping methods) for rNN. Our empirical results validate that joint certification improves the certified accuracy upon individual certification. Moreover, our ISLAND grouping method outperforms the RD method.
Impact of k and r: Figure 3 shows the impact of k and r on the certified accuracy of kNN and rNN, respectively. As the results show, k and r achieve tradeoffs between accuracy under no attacks (i.e., CA(0)) and robustness. Specifically, when k or r is smaller, the accuracy under no attacks, i.e., CA(0), is larger, but the certified accuracy decreases more quickly as the poisoning size e increases.

heading: 5 RELATED WORK

text:
Data poisoning attacks have been proposed against various learning algorithms such as Bayes classifier (Nelson et al., 2008), SVM (Biggio et al., 2012), clustering (Biggio et al., 2013b; 2014), collaborative filtering (Li et al., 2016), regression models (Xiao et al., 2015a; Mei & Zhu, 2015b; Jagielski et al., 2018), LDA (Mei & Zhu, 2015a), neural networks (Muñoz-González et al., 2017; Shafahi et al., 2018; Suciu et al., 2018; Demontis et al., 2019; Zhu et al., 2019; Huang et al., 2020), and others (Rubinstein et al., 2009; Vuurens et al., 2011).
To mitigate data poisoning attacks, many empirical defenses (Cretu et al., 2008; Rubinstein et al., 2009; Barreno et al., 2010; Biggio et al., 2011; Feng et al., 2014; Jagielski et al., 2018; Tran et al., 2018) have been proposed. Steinhardt et al. (2017) derived an upper bound of the loss function for data poisoning attacks when the model is learnt using examples in a feasible set. However, these defenses lack certified robustness guarantees. Recently, several certified defenses (Ma et al., 2019; Rosenfeld et al., 2020; Levine & Feizi, 2020; Jia et al., 2020) were proposed to defend against data poisoning attacks. These defenses provide certified accuracies for a testing dataset either probabilistically (Ma et al., 2019; Jia et al., 2020) or deterministically (Rosenfeld et al., 2020; Levine & Feizi, 2020). All these defenses except (Ma et al., 2019) create majority vote mechanisms to predict the label of a testing example. In particular, a voter is a base classifier learnt on a perturbed version of the training dataset in randomized smoothing based defenses (Rosenfeld et al., 2020), while a voter is a base classifier learnt on a subset of the trainig dataset in DPA (Levine & Feizi, 2020) and bagging (Jia et al., 2020). Ma et al. (2019) showed that a differentially private learning algorithm achieves certified accuracy against data poisoning attacks. They also train multiple differentially private classifiers, but they are not used to predict the label of a testing example via majority vote. Instead, their average accuracy is used to estimate the certified accuracy. kNN and rNN have intrinsic majority vote mechanisms and we show that they provide deterministic certified accuracies against data poisoning attacks. Moreover, rNN enables joint certification. We note that DPA (Levine & Feizi, 2020) proposed to use a hash function to assign training examples into partitions, which is different from our use of hash function. In particular, we use a hash function to rank training examples. Moreover, both DPA and our work rank the labels to break ties when comparing them with respect to their votes.
A line of works (Wilson, 1972; Guyon et al., 1996; Peri et al., 2019; Bahri et al., 2020) leveraged nearest neighbors to clean a training dataset. For instance, Wilson (1972) proposed to remove a training example whose label is not the same as the majority vote among the labels of its 3 nearest neighbors. Peri et al. (2019) proposed to remove a training example whose label is not the mode amongst labels of its k nearest neighbors in the feature space. Bahri et al. (2020) combined kNN with an intermediate layer of a preliminary deep neural network model to filter suspiciously-labeled training examples. Another line of works (Gao et al., 2018; Reeve & Kabán, 2019) studied the resistance of nearest neighbors to random noisy labels. For instance, Gao et al. (2018) analyzed the resistance of kNN to asymmetric label noise and introduced a Robust kNN to deal with noisy labels. Reeve & Kabán (2019) further analyzed the Robust kNN proposed by (Gao et al., 2018) in the setting with unknown asymmetric label noise. kNN and its variants have also been used to defend against adversarial examples (Wang et al., 2018; Sitawarin & Wagner, 2019a; Papernot & McDaniel, 2018; Sitawarin & Wagner, 2019b; Dubey et al., 2019; Yang et al., 2020; Cohen et al., 2020). For instance, Wang et al. (2018) analyzed the robustness of nearest neighbors to adversarial examples and proposed a more robust 1-nearest neighbor. Several works (Amsaleg et al., 2017; Wang et al., 2018; 2019; Yang et al., 2020) proposed adversarial examples to nearest neighbors, e.g., Wang et al. (2019) proposed adversarial examples against 1-nearest neighbor. These works are orthogonal to ours as we focus on analyzing the certified robustness of kNN and rNN against general data poisoning attacks.

heading: 6 CONCLUSION AND FUTURE WORK

text: In this work, we derive the certified robustness of nearest neighbor algorithms, including kNN and rNN, against data poisoning attacks. Moreover, we derive a better lower bound of certified accuracy for rNN via jointly certifying multiple testing examples. Our evaluation results show that 1) both kNN and rNN outperform state-of-the-art certified defenses against data poisoning attacks, and 2) joint certification outperforms individual certification. Interesting future work includes 1) extending joint certification to other learning algorithms, 2) improving joint certification via new grouping methods, and 3) improving certified accuracy of kNN and rNN via new distance metrics.

heading: A PROOF OF THEOREM 2

text:
Proof. We have the following:
CA(e) = min D∗tr∈S(Dtr,e)
∑ (xi,yi)∈Dte I(M(D ∗ tr,xi) = yi)
|Dte| (8) ≥ ∑ (xi,yi)∈Dte minD∗tr∈S(Dtr,e) I(M(D ∗ tr,xi) = yi)
|Dte| (9)
=
∑ (xi,yi)∈Dte I(ai = yi)minD∗tr∈S(Dtr,e) I(M(D ∗ tr,xi) = ai)
|Dte| (10)
=
∑ (xi,yi)∈Dte I(ai = yi)I(e ≤ e ∗ i )
|Dte| , (11)
where the last step is based on applying Theorem 1 to testing input xi.

heading: B PROOF OF THEOREM 4

text:
Proof. We have the following:
CA(e) = min D∗tr∈S(Dtr,e)
∑ (xi,yi)∈Dte I(M(D ∗ tr,xi) = yi)
|Dte| (12)
= min D∗tr∈S(Dtr,e)
∑λ j=1 ∑ (xi,yi)∈Uj I(M(D
∗ tr,xi) = yi)∑λ
j=1 |Uj | (13)
≥ ∑λ j=1 minD∗tr∈S(Dtr,e) ∑ (xi,yi)∈Uj I(M(D ∗ tr,xi) = yi)∑λ
j=1 |Uj | (14)
≥ ∑λ j=1 µj · |Uj |∑λ j=1 |Uj | , (15)
where we have Equation (15) from (14) based on applying Theorem 3 to group Uj .