A law of adversarial risk, interpolation, and label noise
Authors: Daniel Paleka
Amartya Sanyal
Venue: ICLR 2023 poster (2023)
Keywords: label noise
adversarial robustness
lower bound
robust machine learning

Abstract: In supervised learning, it has been shown that label noise in the data can be interpolated without penalties on test accuracy.  We show that interpolating label noise induces adversarial vulnerability, and prove the first theorem showing the relationship between label noise and adversarial risk for any data distribution.  Our results are almost tight if we do not make any assumptions on the inductive bias of the learning algorithm. We then investigate how different components of this problem affect this result including properties of the distribution. We also discuss non-uniform label noise distributions; and prove a new theorem showing uniform label noise induces nearly as large an adversarial risk as the worst poisoning with the same noise rate.  Then, we provide theoretical and empirical evidence that uniform label noise is more harmful than typical real-world label noise.  Finally, we show how inductive biases amplify the effect of label noise and argue the need for future work in this direction.

Published as a conference paper at ICLR 2023
A LAW OF ADVERSARIAL RISK, INTERPOLATION, AND LABEL NOISE
Daniel Paleka
Amartya Sanyal * ETH AT Center, ETH Zurich ama rt.ya sanyal @a .ethz.c ch
ETH Zurich
daniel. wwp.palkkaal weteii.f..thcchhhh
ABSTRACT
In supervised learning, it has been shown that label noise in the data can be interpolated without penalties on test accuracy. We show that interpolating label noise induces adversarial vulnerability, and prove the first theorem showing the relationship between label noise and adversarial risk for any data distribution. Our results are almost tight if we do not make any assumptions of the learning algorithm. We then investigate how different components of this problem affect this result including properties of the distribution. We also discuss non-uniform label noise distributions; and prove a new theorem showing uniform label noise induces nearly large adversarial risk the worst poisoning with the same noise rate. Then, we provide theoretical and empirical evidence that uniform label noise more harmful than typical real-world label noise. Finally, we show how inductive biases amplify the effect of label noise and argue the need for future work in this direction.
the inductive bias
INTRODUCTION
Label noise is ubiquitous in data collected from the real world. Such noise can be result of both malicious intent as well as human error. The well-known work Zhang et al. (2017) observes that training overparameterised neural networks with gradient descent can memorize large amounts of label noise without increased test error. Recently, Bartlett et al. (2020) investigated this phenomenon and termed it benign overfitting: perfect interpolation of the noisy training dataset still leads to satisfactory generalization for overparameterized models. A long series of works (Donhauser et al.) 2022 Hastie et al. 2022 Muthukumar al., 2020) focused on providing generalization guarantees for models that interpolate data under uniform label noise. This suggests that noisy training data does not hurt the test error of overparameterized models.
However, when deploying machine learning systems in the real world, it is not enough to guarantee low test error. Adversarial vulnerability is a practical security threat (Kurakin et al. 2016 Sharif et al. 2016 | Eykholt et al. 2018) for deploying machine learning algorithms in critical environments. An adversarially vulnerable classifier, that accurate on the test distribution, can be forced em on carefully perturbed inputs even when the perturbations are small. This has motivated a large body of work towards improving the adversarial robustness of neural networks (Goodfellow al.) 2014 Papernot et al., 2016 Tramer et al.) 2018: Sanyal et al. 2018 Cisse et al., (017). Despite the empirical advances, the theoretical guarantees on robust defenses are still poorly understood.
Consider the setting of uniformly random label noise. Under certain distributional assump- tions, (anyyal et al. (202T) claim that with moderate amount of label noise, when training classifiers to zero training error, the adversarial risk is always large, even when the test error is low. Exper- imentally, this is supported by /hhu et al. (202T). who showed that common methods for reducing adversarial risk like adversarial training fact does not memorise label noise. However, it is not clear whether their distributional assumptions are realistic, or if their result is tight. To deploy machine learning models responsibly, important understand the extent which common phenomenon like label noise can negatively impact adversarial robustness. In this work, we improve upon previous theoretical results, proving a stronger result on how label noise guarantees adversarial risk for large enough sample size.
"Equal contribution.

---

Published as a conference paper at ICLR 2023
On the other hand, existing experimental results (Sanyal et al. 2021) seem suggest that neural networks suffer from large adversarial risk even in the small sample size regime. Our results show that this phenomenon cannot be explained without further assumptions on the data distributions, the learning algorithm, or the machine learning model. While specific biases of machine learning inductive bias) have usually played "positive" role in ma- chine learning literature (Vaswani et al. 2017]] van Merriënboer et al., [2017] Mingard et al. 22000) we show how some biases can make the model more vulnerable to adversarial risks under noisy interpolation.
models and algorithms (referred
Apart from the data distribution and the inductive biases, we also investigate the role of the label noise model. Uniform label noise, also known as random classification noise (Angluin and Laird 1988], is natural choice for modeling label noise, but it is neither the most realistic nor the most adversarial noise model. Yet, our results show that when it comes to guaranteeing lower bound on adversarial risk for interpolating models, uniform label noise model not much weaker than the optimal poisoning adversary. Our experiments indicate that natural label noise (Wei et al. 2022) is not as bad for adversarial robustness as uniform label noise. Finally, we also attempt to understand the conditions under which such benign (natural) label noise arises.
Overview First, we introduce notation necessary to understand the rest of the paper. Then, we prove theoretical result (Theorem 2 on adversarial risk caused by label noise, significantly im- proving upon previous results (Theorem [ from Sanyal et al. (202I)). In fact, our Theorem 2 gives the first theoretical guarantee that adversarial risk is large for all compactly supported input distri- butions and all interpolating classifiers, in the presence of label noise. Our theorem does not rely on the particular function class or the training method. Then, Section 3 tight without further assumptions, but does not accurately reflect empirical observations on standard datasets. Our hypothesis that the experimentally shown effect of label noise depends on properties of the distribution and the inductive bias of the function class. In Section 4 prove (Theorem 55) that uniform label noise is on the same order of harmfmul as worst case data poisoning, given a slight increase in dataset size and adversarial radius. We also run experiments in Figure 3 showing that mistakes done by human labelers are more benign than the same rate of uniform noise. Finally, in Section 5 we show that the inductive bias of the function class makes the impact of label noise on adversarial vulnerability much stronger and provide an example in Theorem 7
we show Theorem is
2 GUARANTEEING ADVERSARIAL RISK FOR NOISY INTERPOLATORS
Our setting Choose a norm ||-|| on Rd for example I|-112 or II-1lgg- For x E IRd, let (x) denote the bl-ll-ball of radius r around æ. Let j be a distribution on IR and let f C fo. 1} be a measurable ground truth classifier. Then we can define the adversarial risk of any classifier f with respect to f", ne, given an adversary with perturbation budget > 0 under the norm ||-1|, as
(S. Parp Ez E Bp(x), ('(x) * f(z)))
(1)
Next, consider training set ((21,))),.... ........ ( (Zm,
Vm in d x {0, 13, where the
independently
sampled from μr, and each yi equals f"(z;) with probability - 77. where 7) >> O is the label noise rate. Let f be any classifier which correctly interpolates the training set. We now state the main theoretical result of Sanyal et al. (202I) so that we can compare our result with it.
Theorem ( (Sanyal et al. 2021
Suppose that there exist e₁ 2 C2 > 0. p > 0, and a finite set
< C Rd satisfying
(U BEC
2 and E S, (Bp/2(5)) 2
(2)
K
Further, suppose that each of these balls contains points from a single class. Then for 8 > 0, when
the number of samples 2 1s_ log 144). with probability 1 1-6
nea
RAdv, (S,P) 2 C1-
(3)
2

---

Published as a conference paper at ICLR 2023
This is the first guarantee for adversarial risk caused by label noise in the literature. However, Theorem has two extremely strong assumptions:
The input distribution has mass e₁ in union of balls, each of which has mass at least C2;
Each ball only contains points from a single class.
It is not clear why such balls would exist for real-world datasets, or even MNIST CIFAR-10. In Appendix F. we give some evidence against the second assumption in particular. In Theorem 2 remove these assumptions and show that our guarantees hold for all compactly supported input distributions, with comparable guarantees on adversarial risk.
Let C be compact subset of Rd An important quantity in our theorem will be the covering number N = (p/22; C, II-II) of C in the metric ||-1|- The covering number N is the minimum number of ||-|-balls of radius p/2 such that their union contains C. For any distribution μ on Idd denote by (C) = 2~ [ar E CJ the mass of the distribution contained in the compact C.
Theorem 2. Let Rd satisfy plC) > O, and let N (p/2,C, II-Il) be its covering number. For
2N log 8 with probability 1 - 8 we have that 6 > 0, when the number of samples satisfies m p(C)g
8N
1 RAdv (s 2 4 (C)
(4)
for any classifier f that interpolates the training set.
The compact C can be chosen freely, allowing us to make tradeoffs between the required number of samples and the lower bound on the adversarial risk. As the chosen C expands in volume, the lower bound on the adversarial risk μ (C) also increases. However, this also increases the required number of samples for the theorem to kick in, which depends its covering number N. The tradeoff curve depends on the distribution μr; we discuss this in Section 3
Note that Theorem 2 is easier interpret than Theorem D it holds for any compact C opposed to a finite set Ç of dense balls. Our result avoids the unwieldy assumptions, and in fact gives a slightly stronger guarantee than Theorem When Equation (2) holds, note that we can choose the Thus, under similar
compact C = Ueec (s)) from Theorem yielding N = |c] and μ (C)
settings the previous result, our theorem requires the number of samples m 52
[cl nej
which is
smaller than m = i
[<]
required in Theorem
7/2
We leave the proof of Theorem to Appendix but we provide brief sketch of the ideas.
Proof sketch We want to prove that a large portion of points from j have mislabeled point nearby when is large enough. The expected number of label noise train- ing points is rym; however priori those could be any- where in the support of p.
The key idea is that we can always find set of |l-ll-balls covering a lot of measure, with each of the balls having a large enough density of μ. We prove this in Lemma [ and provide an illustration in Figure [ The blue dotted circles in Figure I are the ll-ll-balls; they do not cover the entire space but cover a significant portion of the entire density. Then, if we take a lot of balls with large density of a single class, we can prove that label noise induces an opposite-labeles labeled point in each of the chosen balls given m large enough.
Depending on the covering number of C, small number of I|-II- balls of sufficient density cover a lot of the measure of C. Label noise makes every point drawn from the covered set adversarially vulnerable.
Figure 1:
Concretely, the probability for a single chosen ball to not be adversarially vulnerable is on the order of and summing this up over the O(N)
(1-2%) -. chosen balls goes zero when m is large. By the union bound, each of these balls is then adversarially vulnera- ble, summing up to constant adversarial risk.
v((C) )
3

---

Published as a conference paper at ICLR 2023
O 001
0,034
0.001
0.004
Tolk
Trans
Trans
Toud
Test
Texd
56.1 (abel noise)
10.
nobos)
1 (Sbel noam)
1) [bieel nobm)
[bbbl nose)
1) (bitel noom)
(a) MNIST
(b) Re (CIFARIO)
(c) DenseNet121 (CIFARIO)
Figure 2: From Sanyal al. (021) Adversarial error increases with increasing label noise v (x- axis) at rate much faster than predicted by Theorem 2 the current paper). The label noise is synthetically injected in the training with probability n).
Here, is the perturbation magnitude (p in
We considered the binary classification case for simplicity. The proof in Appendix A lower bounds the adversarial risk on single true class. Thus, by summing up the risks for each class, we lose only a constant factor on the guaranteed adversarial risk in the multi-class case.
For compactly supported μt, we can take C to be the support of μ to prove a general statement. Corollary 3. Let N be the covering number of Supp(μ) with balls of radius p/2. For ō > when the number of samples satisfies 8N log 2N with probability 1 - 5 we have that
n
RAdv,p (f.P) 4
(5)
This is easier to understand than Theorem if interpolating dataset with label noise, the number of samples required to guarantee constant adversarial risk scales with the covering number of the support of the distribution.
Remark The proof in Appendix A actually proves Equation 4 by first proving a stronger fact: if plee is the normalized restricton of μ C, then
1 4'
RAdv.p (f.
(6)
We can use this to give better guarantees when f is not robust. If region of supp(μ) is already adversarially vulnerable using the true classifier f*, we can omit it from C, and just add the guarantee from Theorem 2 the original adversarial risk to get stronger lower bound on (ff.
PRACTICAL IMPLICATIONS ON SAMPLE SIZE
In this section, discuss the limitations of results like Theorem When we allow arbitrary interpo- lating classifiers, we show that Theorem 2 paints an accurate picture of the interaction of label noise, interpolation, and adversarial risk. However, this particular theoretical framework cannot explain the strong effect of label noise on adversarial risk in practice (see Figure 2 We argue that this requires a better understanding of the inductive biases of the hypothesis class and the optimization algorithm.
The number of required samples in Theorem 2 can be very large, depending on the density and the covering number of the chosen compact C. Consider ||-II to be the I1 norm, as is customary in adversarial robustness research (Goodfellow et al. 2014]. Then the balls B, small hypercubes in Rd If we choose C to be the hypercube (0. 1 the covering number scales exponentially in dimension:
Required sample size for Theorem 2
(
N [o,
A rough back-of-the-envelope calculation indicates that this can scale badly even for standard
datasets such as MNIST (d = 784) or CIFAR-I0 (d 3072), since Theorem 2 we need vn 2 .N p[C This amounts an impossibly large sample size (m Z 10784) for & 0.2 to explain
the effect already observed with in 50000 MNIST training samples in Figure 2a
4

---

Published as a conference paper at ICLR 2023
Hence result often does not guarantee any adversarial risk if the number of samples is small. In general, the covering number of dataset is not polynomial in the dimension, except if the data has special properties in the given metric. For example, if the data distribution is supported on a subspace of R2 of ambient dimension k < d, we can pick a C for which the covering number in I1-1lp will depend only I and not on d. However, this is still not sufficient explain the behaviour in Figures [2b and 2g If our result indeed kicks in for some ambient dimension &s with DenseNet121 on CIFARIO, then for a given adversarial risk (say 80%), the power law dependence
would imply (#= ~ "2" where label noise rate yields adversarial error 80% with perturbation
budget Pi- With another tock-of-the-envllyy calculation using Figure
2c we set 17 722 0.7, 0.1
and P1: = 0.001, 0.004. This yields an ambient dimension k 2, which is unrealistic for CIFAR-10.
These calculations suggest the possibility that a tighter bound than Theorem 2 might exist. However, the large sample size not just a limitation of "Thoormmm2 [ and distributions are allowed, the adversarial risk cannot be lower bounded for poly(d).
In fact, we show that arbitrary classifiers
Our result is tight is a priori possible that the true dependence of adversarial risk on label noise kicks in for much lower sample size regimes than in Theorem 2 This might suggest that the lower bound on sample complexity can be improved. We show this is not the case and in fact our bound sharp. In particular, we design simple distribution on E2 such that there exist classifiers which correctly and robustly interpolate datasets with the number of samples m exponential in d.
Proposition 4. Lel 11 be the uniform distribution on Sd-1 {-1.-.., Fd E IRd xf
+..4 +... =1. and let the ground truth classifier I" be threshold function x1: f*(x) =1=1 1 Consider any adversarial radius p < in the Euclidean metric. Then, for any label noise rj 1: with high probability, there exists a classifier f that interpolates m [1.01]] samples from the label noise distribution, such that Rlfv.plf.Pt oc(1).
Proof sketch The main ingredient of the proof is the concentration of measure on Sd-1, which makes the training samples far apart the Fuclidean metric. We leave the full proof to Appendix B Similar statements in the clean data setting have appeared before, e.g. in Bubeck and Sellke (2021).
Note that Proposition f shows a construction where Theorem 2 cannot guarantee an adversarial risk lower bound with sample size m sub-exponential in d. Hence, the covering number of any substantial portion of gd-1 exponential the dimension d. This unintentionally proves the well known fact that the covering number of the sphere grt in the Euclidean metric is exponential
Optimizing C can avoid large sample size While Proposition shows the tightness of Theorem 2 in the worst case, it is possible a smaller sample size requirement sufficient under certain condi- tions. In particular, if we can pick a compact with small covering number, such that the measure (C)) is large, then Theorem allows for small sample size while guaranteeing large adversarial risk.
Example Take an adversarial radius p > in the I1-Il,o metric and choose e (0, f). let μ (1 -r)m + rp2 be the average of two measures, and p2, with μn the uniform distribution on [0, 1]d, and μl the uniform distribution on a smaller hypercube [0, p|
The first choice C = [0, 1 as in Corollary 3 has covering number on the order of pnd Theorem 2 is then vacuous until m 2 p -dd "//,, which is very large in high dimensions. Note that this is necessary to achieve the lower bound of adversarial risk of q. However, if we only want to guarantee an adversarial risk of 7 instead we can use C [0, p] For this, the covering number is 1 and we
use Theorem 2 for =0 O (+) This suggests that while the required sample size for the maximal adversarial risk is possibly very large, it can be much smaller, depending on the distribution, for guaranteeing a smaller adversarial risk.
See Proposition 4.16 in rbaea http:///wwbbahheetecccchgggg//ee material anterial//ecttre04..0
5

---

Published as a conference paper at ICLR 2023
Formally, to get the "best possible" m in Theorem 2 for certain adversarial risk lower bound r, should solve the following optimization problem over subsets of supp(μ):
N I1-ll>e) log N 12/
min (C)) 4
(8)
p²()
The above optimization problem comes from substituting into the adversarial risk placeholder in Theorem[] Equation (8) provides a complexity measure to get tighter lower bounds on the adversar- ial vulnerability induced by uniform label noise. is not known whether the optimization tractable in general. However, the concept of having to solve an optimization problem in order to get a tight lower bound common in the literature. Some examples are the representation dimension (Beimel et al. 2019) and the SQ dimension (Feldman 2017)
To conclude, this section shows that in real world data, the required sample size for guaranteeing large adversarial risk from interpolating label noise is significantly smaller than what an off-the-shelff application of Theorem 2 might suggest. However, we also proved that is not possible to obtain tighter bounds without further assumptions on the data or the model.
4 NON-UNIFORM LABEL NOISE
In previous sections, we discussed guaranteeing a lower bound adversarial error for noisy inter- polators in Section 2 In Section 3. we discussed the tightness the said bound. However, all of these results assumed that the label noise is distributed uniformly on the points in the training set, which corresponds to the popular Random Classification Noise (Angluin and Laird 1988) model. However, an uniform noise model is not very realistic (Hedderich et al.) [02 Wei et al. 2022); ); and it is thus sensible to also investigate how our results change under non-uniform label noise models.
Uniform noise is almost as harmful as poisoning The worst-case non-uniform label noise model is data poisoning, where an adversary can choose the labels of a subset of the training set of fixed size (see Biggio and Roli (2018) for survey). is well known that flipping the label of a constant number of points in the training set can significantly increase the error of a logistic regression model (Jagielski et al., 2018)) or an SVM classifier (Biggio et al.] 201T). On the contrary, the test error of a neural networks has been surprisingly difficult to hurt by data poisoning attacks which flip small fraction of the labels. Lu et al. (2022) show that, on some datasets, the effect adversarial data poisoning test accuracy is, fact, comparable to the effect of uniform label noise.
We phrase the main result of this section informally in Theorem 5 using standard game-theoretic metaphors for data poisoning, and defer the formal version to Appendix C Let again μ be a distri- bution on IRd and f a correct binary classifier, and let 17 be the label noise rate. Consider a game in which an adversary flips the labels of subset of the training set, and tries to maximize the mini- mum adversarial risk among all interpolators of the noisy (after flipping labels) training set. We will compare the performances of two adversaries:
Uniform, who samples T points uniformly from the distribution, and flips the label of each the T' points in the sampled training set with probability Ty.
Poisoner, who inserts N rym arbitrary points from supp(u) with flipped labels into the training set and then samples the remaining m - N points uniformly, with correct labels.
Here T' and m are the respective training set sizes. If ~ 7 = m, then the two adversaries flip the same number of labels in expectation. In that sense, both of these adversaries have the same budget. However, the Poisoner can choose which points to flip and thus intuitively, in this regime, the Poisoner will get a higher adversarial risk than the Uniform. Surprisingly, we can prove the Uniform is not much worse if T
log m.
Theorem 5 (Informal statement of Theorem ITI. Denote the adversarial risks of the Uniform and the Poisoner adversaries by R Unif and R Poison respectively. For any > O, we have that
Unif R2p
R Poison
(9)
as long as Poison (11) and T 2 log m.

---

Published as a conference paper at ICLR 2023
Roughly speaking, the above theorem shows that if the Uniform adversary is given double the ad- versarial radius and a log factor increase on the training set size, then Uniform can guarantee an adversarial risk of the same magnitude the Poisoner. The full statement and the proof of the theorem are given in Appendix C but we provide a brief sketch here.
Proof sketch The Poisoner will choose N points to flip, adversarially poisoning every point in the N corresponding p-balls. As in Theorem 2 we can use Lemma show that subset of the balls with density RQ1/N) covers half of the adversarially vulnerable region. Then Uniform samples T points, and we expect to hit each of the balls in the chosen subset. Because of the doubled radius, each sampled point makes the the whole p-ball vulnerable. The log factor comes from the same reason as in the standard coupon collector (balls and bins) problem; if we have N bins with hitting probabilities 12(1/N), then we need 12(N log N) tries to hit each bin at least once.
Some label noise models are benign Different label noise models with the same expected label noise rate can have very different effects on the adversarial risk. In the previous sections, we showed that uniform label noise is almost as bad as the worst possible noise model with the same label noise rate. This raises the question whether all noise models are as harmful as the uniform label noise model. We answer the question in the negative especially for data distributions that have long tailed structure: many far-apart low-density subpopulations in the support of the distribution μr
For this, we show a simple data distribution μu in Proposition 6 where:
Uniform label noise with probability 1) guarantees adversarial risk on the order of mp; A different label noise model, with expected label noise rate 77, which affects only the long tail of the distribution μ can be interpolated with o(1) ad adversarial risk.
We argue that this is neither unrealistic distributional assumption nor impractical noise model. In fact, most standard image datasets, like SUN (Xiao et al., 2010), PASCAL (Everingham et al.) 2010), and CelebA (Liu is natural to assume that mistakes in the datasets are more likely to occur in the long tail, where the data points are atypical. In Feldman (2020). was argued that noisy labels on the long tail are one of the reasons for why overparameterized neural networks remember the training data. Formally, we prove the following regarding the benign noise model for a long-tailed distribution.
2015) have long tail (Zhu al. 2014 Sanyal al. [022). Moreover,
Proposition 6. Let A <. B be integers with A much smaller than B. Let p be mixture model on I supported on a disjoint union of A + B intervals, such that half of the mass is on the first A intervals and half of the mass is on the last B intervals:
1 Σ
B 2B E Unif (A (A+)A++++) 1
1 2A
Unif 1
Let the ground truth label be zero everywhere. Sample two datasets D1, D2 of size from μ using two different label noise distributions: For D flp the label of each sample x E [0, A B] indepen- dently with probability 17. For DD,, flip the label of each sample probability 2n, and leave the labels of the other samples unchanged. Then, for any p, 8 E (0, for the number of samples m = (A) (ignoring log terms), we have that with probability
[A, B) independently with
8:
* For any f which interpolates D1, the adversarial risk is large: RAdv, (f, (4) = Q2 (1).
There exists ʃ which interpolates D2, such that Radv. = O, (4)
A similar distribution was previously used as representative long tailed distribution in the context of privacy and fairness in Sanyal et al.] (2022). Our result can also be extended to more compli- cated longetailed distributions with similar strategy. Proposition 6 implies that the the first noise model (for D1) induces (211 adversarial risk on all interpolators. On the other hand, for the second noise model i.c. for D2, it is possible to obtain interpolators with adversarial risk on the order of (4). Thus, for distributions where A < B, this implics the existence of almost robust interpolators despite having the same label noise rate.
Real-world noise is more benign than uniform label noise To support our argument that real world noise models are, in fact, more benign than uniform noise models, consider the noise
7

---

Published as a conference paper at ICLR 2023
100
102
Avg. Memorisation Score
Human mislabeled led All tamples
Advensara Error
Adversoraa Errur
0.3
0.2
40
82
Clean
Clcan
0.1
20
Unitonn
fnrf
0.001
Perurbatioo Budget
0.009
5,009
6:01
0.001
Perturbation Budget
0,033
3.509
0.61
airpians
automstale
brdd
frog
hore
ship
(a) CIFARIO
(b) CIFARIOO
(c) CIFARIO
Figure 3: Figures 3a and 3b plots adversarial risk against perturbation budget on CIFARIO
and CIFAR 100 datasets respectively, with three label noise models. Clean denotes the original CIFAR- 10/100 labels. Human denotes the numan-geeneatie refers to uniformly random label noise with the same rate as Human. Figure [C plots the average memorisation score per class for: Human mislabeled examples i.e. examples with Human noisy labels and All samples. The horizontal line is the average across all classes. The higher score of human mislabeled examples indicates that those examples belong to the long tail of the distribution.
labels from (Wei al. 2022). Uniform
induced by human annotators in Wei et al. (0022). They propose new version of the CIFAR 10/100 00 dataset (Krizhevsky et al. (2009) where each image is labelled by three human annotators. Known as LUFAR-I0/100-1 each example's 's label is decided by a majority vote on the three annotated labels. We train ResNet34 models till interpolation on these two datasets. The label noise rate, after the majority vote, is ~ 9% in CIFARIO and = 40% in CIFAR100. We repeat the same experiment for uniform label noise with the same noise rates, and also without any label noise. Each of these models' adversarial error is evaluated with an foo PGD adversary plotted in Figures and 3b)
Figures 3a and 3b show that, for both CIFAR 10 and CIFAR100, uniform label noise indeed worse for adversarial risk than human-generated label noise. For CIFAR-10, the model that interpolates human-generater label noise is almost as robust as the model trained on clean data. This supports our argument that real-world label noise is more benign, for adversarial risk, than uniform label noise.
An important direction for future research is understanding what types of label noise models are useful mathematical proxies for realistic label noise. We shed some light on this question using the idea of memorisation score (Feldman and Zhang 2020). Informally, memorisation score quantifies the atypicality of sample; it measures the increase in the loss on data point when the learning algorithm does not observe it during training compared to when it does. A high memorisation score indicates that the point is unique in the training data and thus, likely, lies in the long tail of the distribution. In Figure 3c we plot the average memorisation score of each class of CIFARIO in brown, and the average for images that were mislabeled by the human annotator in blue. It is clearly evident that the mislabeled images have higher memorisation score. This supports our hypothesis (also in |Feldman (2020)) that, in the real world, examples in the long tail, are more likely to be mislabeled.
5 THE ROLE OF INDUCTIVE BIAS
We have seen, in Section 3 that without further assumptions the theoretical guarantees in Theorem 2 only hold for very large training sets. In this section, we discuss how the inductive bias of the hypothesis class or the learning algorithm can lower the sample size requirement and point to recent work that indicates the presence of such inductive biases in neural networks.
Inductive bias can hurt robustness even further There is ample empirical evidence (Ortiz-) Jimenez et al. 2020; Kalimeris et al.) 2019: Shamir et al. 2021) that neural networks exhibit an inductive bias that is different from what is required for robustness. Shah et al. (2020) also provides empirical evidence that neural networks exhibit certain inductive bias, that they call simplicity bias, that hurts adversarial robustness. Drtiz-Jiménes. et al. (2022) show that this is also responsible for phenomenon known catastrophic overfitting.
8

---

Published as a conference paper at ICLR 2023
Figure 4: Visualization of a portion of the distribution μ and the hypothesis class H used Theo- rem 7 The crosses the mislabeled examples and the circles are correctly labelled examples. All the circles are adversarially vulnerable to upwards perturbations of magnitude less than p.
Here, we show simple example illustrate the role of inductive bias. Consider binary classifi- cation problem on data distribution j and a dataset Sm.;, of m points, sampled i..d. from μ such that the label of each example is flipped with probability 17-
Theorem 7. For any >> O, there exists a distribution on R.2 and two hypothesis classes H and F. such that for any label noise rate yj E 1/2 and dataset size m θ ( in expectation we have that: for all h E H. that interpolate Sm.n.
Radv, (h. p)) 2 Q1);
(10)
whereas there exists an f E F that interpolates Sm. and Rav. (f:u)= = (
The classes H and F are precisely defined in Appendix F where formal proof is given well, but we provide a proof sketch here. The data distribution in Theorem 7 is uniform on the set [0, W] {0). that is, the data just supported on the first coordinate where W > > O. The ground truth is threshold function on the first coordinate. The constructed f E F simply labels threshold function on the first coor-
everything according to the ground truth classifier (which dinate) except the mislabeled data points; where it constructs infinitesimally small intervals around the point on the first coordinate. Note that this construction is similar to the one in Proposition [ By design, it interpolates the training set and its expected adversarial risk is upper bounded by 2mmn..
Each hypothesis in the hypothesis class H can be thought of as union of T-shaped decision regions. The region inside the T-shaped regions are classified as 1 and the rest as O. Note that the "head" of a T-shaped region make the region on the data manifold (first coordinate) directly below them adversarially vulnerable. The width of the T can be interpreted as the inductive bias of the learning algorithm. The decision boundaries of neural networks usually lie on the data manifold (Somepalli eet al. 2022); ; and the network behaves more smoothly off the data manifold. A natural consequence of this is that the head of the Ts are large. This is not the exact explanation of inductive bias in neural networks, but rather an illustrative example for what might be happening in practice. In Appendix G we provide experimental evidence to show this type of behaviour for neural networks.
There are two important properties of this simple example relevant for understanding adversarial vulnerability of neural networks. First, the adversarial examples constructed here are off-manifold: they do not lie on the manifold of the data. This has been observed prior works (Hendrycks) and Gimpel| 2016 (anyal et al.] [0188] Khoury and HadfieldMMenell 2018). Second, our examples implicitly exhibit the dimpled manifold phenomenon recently described in Shamir et al. (2021).
Is Theorem 2 about the wrong function class? When fitting deep neural networks to real datasets, the results of Theorem 2 still hold even when the number of samples m is much smaller than required, as can be seen in Figure] 2 We think that proving guarantees on adversarial risk in the presence of label noise is within reach for simple neural network settings. Towards this goal, we propose a conjecture in a similar vein to Bubeck et al. (2020):
Conjecture 1. Let : Id + E be a neural network with a single hidden layer with neurons. Under the same conditions as Theorem for the number samples mn = 20 poly (k, d)),
RAdv,p 2 const.
(11)
for a distribution μ supported on [0, 1]a.
In short, we conjecture that neural networks exhibit inductive biases which hurt robustness when in- terpolating label noise. [ohmatob] (202T) show a similar result for a large class of neural networks. However, the Bayes optimal error in their setting is positive constant (as opposed to zero in our setting), and we assume uniform label noise in the training set. Understanding these properties is important for training on
data, where label noise is not possibility but rather norm.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
Amartya Sanyal acknowledges the ETH AI Center for the postdoctoral fellowship. We thank Mislav Balunović for discussing and checking the proof of Theorem 2 Domagoj Bradač for discussing Lemma 8
and Jacob Clarysse and Florian Tramer for general feedback.
REFERENCES
Dana Angluin and Philip Laird. Learning from noisy examples. Machine Learning, 1988.
Peter I. Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 2020.
Amos Beimel, Kobbi Nissim, and Uni Stemmer. Characterizing the sample complexity of pure private learners. Journal of Machine Learning Research, 2019.
Battista Biggio and Fabio Roli. Wild patterns: Ten years after the rise of adversarial machine learning. Patlern Recognition, 84:317-331, 2018.
Battista Biggio, Blaine Nelson, and Pavel Laskov. Support vector machines under adversarial label noise. In Asian Conference on Machine Learning, pages 97-112. PMLR, 2011.
Sebastien Bubeck and Mark Sellke. A universal law of robustness via isoperimetry. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Sébastien Bubeck, Yuanzhi Li, and Dheeraj Nagaraj. A law of robustness for two-layers neural networks. arXiv:2009. /4444, 2020.
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks: Improving robustness to adversarial examples. In International Conference on Machine Learning (ICML), 2017.
Elvis Dohmatob. Fundamental tradeoff's between memorization and robustness in random features and neural tangent regimes, 2021.
Konstantin Donhauser, Nicolo Ruggeri, Stefan Stojanovic, and Fanny Yang. Fast rates for noisy interpolation require rethinking the effects of inductive bias. In International Conference on Machine Learning (ICML), 2022.
Mark Everingham, Luc Van Gool, Christopher KI Williams, John Winn, and Andrew Zisserman. The PASCAL Visual Object Classes (VOC) challenge. 2010.
Kevin Eykholt, Ivan Evtimov, Earlence Fernandes, Bo Li, Amir Rahmati, Chaowei Xiao, Atul Prakash, Tadayoshi Kohno, and Dawn Song. Robust physical-world attacks on deep learning visual classification. In Proceedings of the IEEE conference on computer vision and pattern recognition (CVPR), 2018.
Vitaly Feldman. general characterization of the statistical query complexity. In Conference on Learning Theory (COLT), 2017.
Vitaly Feldman. Does learning require memorization? a short tale about long tail. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 954-959, 2020.
Vitaly Feldman and Chiyuan Zhang. What neural networks memorize and why: Discovering the long tail via influence estimation. Advances in Neural Information Processing Systems, 2020.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv:1412.657.. 2014.
Trevor Hastic, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. The Annals of Statistics, 2022.
Michael A Hedderich, Dawei Zhu, and Dietrich Klakow, Analysing the noise model error for real- istic noisy label data. In Proceedings of the AAAI Conference Artificial Intelligence, 2021.
10

---

Published as a conference paper at ICLR 2023
Dan Hendrycks and Kevin Gimpel. A baseline for detecting misclassified and examples in neural networks. In International Conference on Learning Representations (ICLR), 2016.
Matthew Jagielski, Alina Oprea, Battista Biggio, Chang Liu, Cristina Nita-Rotaru, and Bo Li. Ma- nipulating machine learning: Poisoning attacks and countermeasures for regression learning. In 2018 IEEE Symposium Security and Privacy (SP), pages 19-35. IEEE, 2018.
Dimitris Kalimeris, Gal Kaplun, Preetum Nakkiran, Benjamin Edelman, Tristan Yang, Boaz Barak, and Haofeng Zhang. Sgd on neural networks learns functions of increasing complexity. Advances in Neural Information Processing Systems (NeurlPS), 2019.
Mare Khoury and Dylan Hadfield-Menell. On the geometry of adversarial examples. arXiv preprint arXiv: /8/ 1.00255, 2018.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
A Kurakin, I Goodfellow, and S Bengio. Adversarial examples in the physical world. arXiv: 2016.
B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by model selection. The Annals of Statistics, 2000.
Ziwei Liu, Ping Luo. Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of International Conference on Computer Vision (ICCV), 2015.
Yiwei Lu, Gautam Kamath, and Yaoliang Yu. Indiscriminate data poisoning attacks on neural net- works, 2022.
Chris Mingard, Joar Skalse, Guillermo Valle-Pérez, David Martinez-Rubie Vladimir Mikulik, and Ard A. Louis. Neural networks are a priori biased towards boolean functions with low entropy. In International Conference on Learning Representations (ICLR), 2020.
Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu, and Anant Sahai. Classification vs regression in overparameterized regimes: Does the loss function matter? arXiv:2005. 08054, 2020.
Guillermo Ortiz-Jimenez Apostolos Modas, Seyed-Mohsen Mohsen Moosavi, and Pascal Frossard. Neural anisotropy directions. Advances in Neural Information Processing Systems, 33:17896-17906 2020.
Guillermo Ortiz-Jiménez, Pau de Jorge, Amartya Sanyal, Adel Bibi, Puneet K Dokania, Pascal Frossard, Gregory Rogéz, and Philip HS Torr. Catastrophic overfitting is bug but also a feature. arXiv preprini 1rXiv:2206.08222 2022.
Nicolas Papernot, Patrick McDaniel, Xi Wu, Somesh Jha, and Ananthram Swami. Distillation as a defense to adversarial perturbations against deep neural networks. In IEEE Symposium on Security and Privacy (SP), 2016.
Amartya Sanyal, Varun Kanade, Philip HS Torr, and Puneet K Dokania. Robustness via deep low- 2018.
rank representations.
Amartya Sanyal, Puneet K. Dokania, Varun Kanade, and Philip Torr. How benign is benign overfit- ting? In International Conference on Learning Representations (ICLR), 2021.
Amartya Sanyal, Yaxi Hu, and Fanny Yang. How unfair is private learning? In Proceedings of the Thirty-Eghuth Conference on Uncertainty in Artificial Intelligence, 2022.
Harshay Shah, Kaustav Tamuly, Aditi Raghunathan, Prateck Jain, and Praneeth Netrapalli. The pitfalls of simplicity bias in neural networks. Advances in Neural Information Processing Sys- tems (NeurIPS), 2020.
Adi Shamir, Odelia Melamed, and Oriel BenShmuel. The dimpled manifold model of adversarial examples in machine learning. arXiv:2106. 2021.

---

Published as a conference paper at ICLR 2023
Mahmood Sharif, Sruti Bhagavatula, Lujo Bauer, and Michael K Reiter. Accessorize crime: Real and stealthy attacks on state-of-the-ar face recognition. Proceedings of the 2016 ACM SIGSAC Conference computer and communications security, 2016.
Gowthami Somepalli, Liam Fowl, Arpit Bansal, Ping Yeh-Chiang, Yehuda Dar. Richard Baraniuk, Micah Goldblum, and Tom Goldstein. Can neural nets learn the same model twice? Investigating reproducibility and double descent from the decision boundary perspective. arXiv:2203.08124 2022.
Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick Mc- Daniel. Ensemble adversarial training: Attacks and defenses. International Conference on Learning Representations (ICLR), 2018.
Bart van Merriënboer, Amartya Sanyal, Hugo Larochelle, and Yoshua Bengio. Multiscale sequence modeling with a learned dictionary. VrXiv:1707.00700 2017.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances Neural Informa- tion Processing Systems (NeurIPS), 2017.
Jiaheng Wei, Zhaowei Zhu, Hao Cheng. Tongliang Liu, Gang Niu, and Yang Liu. Learning with noisy labels revisited: A study using real-world human annotations. International Conference Learning Representations, 2022.
Jianxiong Xiao, James Hays, Krista A Ehinger, Aude Oliva, and Antonio Torralba. Sun database: Large-scale scene recognition from abbey to zoo. IEEE, 2010.
Chiyuan Zhang, Samy Bengio, Moritz Hardt. Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. International Conference on Learning Rep- resentations (ICLR), 2017.
Jianing Zhu, Jingfeng Zhang, Bo Han, Tongliang Liu, Gang Niu, Hongxia Yang, Mohan Kankan- halli, and Masashi Sugiyama. Understanding the interaction of adversarial training with noisy labels. arXiv preprint 202::2102.0344: 2021.
Xiangxin Zhu, Dragomir Anguelov, and Deva Ramanan. Capturing long-tail distributions of object subcategories. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recogni- tion, pages 915-922, 2014.
12

---

1 Published as a conference paper at ICLR 2023
A PROOF OF THEOREM 2
Here we prove the following statement:
Theorem 2. Let C TRd satisfy plC) > O, and let N N=, be its covering number. For > O, when the number of samples satisfies m 2
SN pic)
with probability we have that log 8.
2N
1 RAdv oe (f. (00)24u66 ((()
(4)
for any classifier f that interpolates the training set.
For notational convenience, we replace p by 2p in all places for the proof below.
Proof. Without loss of generality, let Co { x E: (x) 0 have probability p(Co) 2 LC(C).
Let Ho = plc., normalized so that (o(CC) = 1.
By Chernoff, with probability 1 - exp
(c()m 16
2
2. at least my = |[(mm of the samples
2; are in Co. Without loss of generality, let 21...., Zmp be those samples. Then
1
2p 2p (f,M) 2
(C)) P PaNaREECo B3 E (2)( (*) + f(z))]
(12)
2
1
((C) Pawue [Ex E B2o(2), f(z) + 0]
(13)
2
1
2 (C)) PæENA [ mg
2, E B2p (z) n Co, f(z;) + 0]
(14)
2
1
2 JC(C) Pamau
[i < my
x E B2p zi Co, f(z,) + 0].
(15)
2 ((C) po
U
(2p
(16)
iSmo, f(21)
Let $1...., & be the centers of minimum p-covering of Co.
((=)) The plan is the following: we will lower bound S(z)zu) (2; by the union of some (sx), which will have large po mo-muue in total. Moreover, each of the chosen (sx) will have large enough measuree. For this, we use the following general lemma:
Lemma 8. Let , SN be the centers of some balls (,, in Rd and take any measure v. Then, for any constant 0 < < 1, there exists subset S {1,...,, N of the balls such that:
v (Uies (s:)) 2 (1 - aa) (U (s())) (,
(B, $ B,(s)) for for all i E S.
Informally, the first condition says that the union of the chosen subset has a constant fraction of the measure of the union. The second condition says that each of the chosen balls has Q21/N) of the measure the union of all balls.
Proof. Without loss of generality, let the balls be ordered by measure:
(B)(s))) 2 v (B.(sz)) 2 (sN))
(17)
13

---

Published as a conference paper at ICLR 2023
a) The original cover of
b) The dense greedy subcover.
Figure 5: Illustration of Lemma 8 and Corollary 9 Given a cover N balls, we can pick subcover of balls covering at least half of the measure, with each ball having measure at least 2N
We take the greedy subset (1....,K K} where S
S N the largest index such that
(sx)) 2 a (U (,)))).
K =
U (si)
U (si)
U
(B(
(18)
N=K+1
U (,i)
(N
K) a
(..)s))
(19)
N
1=1
N
2 (1 a)
(,:)
(20)
The first inequality follows because for all i 2 K + 1 holds v (Bx)) av (U B.(s.))
and the second because N-K < 1.
We can apply the above to the situation in the proof of Theorem with 2- Without loss of generality, order the covering 81, .1...., 8N by the yo-measure the corresponding balls:
Pi (B)(s))) 2 pio (8)) 2 2 140 (#x))
(21)
Corollary 9. 1f1 < K < N is the largest index such that no (5, 2 1 then
2N.
(UB(SS))
K
No k=1
(22)
We now show that the chosen balls are dense enough to get samples in the training set with high probability.
Lemma 10. With probability - 8/2, each (8( for k & contains at least one z; E Co such that f(z;) * O.
Proof. We have
P [zz E (8(()) E Col > 2N
(23)
and because the label corruption is independent from everything, we also have
PP [f(x)) + Col 1
(24)
= P (fx))) + and z; B,(B)) 2; E Co) >
(25)
2N
14

---

Published as a conference paper at ICLR 2023
Therefore,
P [B O { ma, f(zi) + 0} = =0]
(26)
mhg
II P 12 & Bp(sk) or 2, $ Cu f(z,) + 0
(27)
$
(28)
2N
ma7
$ exp
(29)
2N
2N
In the last line we used + I c², the fact that mo 1 ((Cmm, and the expression for m from Theorem 2 Now we can use the union bound to prove the lemma:
S K 8
IP| some (p(8k) for k < K contains no z, S mo: f(z)) #0]
S
6.
(30)
N
Finally, using both Lemma and Lemma 10 we can finish:
(fdv
(u()) no
U
Bap(zi)
(31)
ismo: f(Er)=00
K
1
(C)) po BB((s))
2 (c).
(32)
2
B PROOF OF PROPOSITION 4
be the uniform distribution [x1....,2 Id E IRd x +... x2 13, and let the ground truth classifier f be a threshold function on Fı; (xxx = -1,,2 1. Consider any adversarial radius < 1 in the Euclidean metric. Then, for any label noise n, < 1: with high probability, there exists a classifier f that interpolates m 1.001 samples from the label noise distribution, such that RAdv, .)) oa(1).
Proposition 4. Let
Sd-1
Proof. Let the m 1.01 < (xp(d/80) samples be 21...., Zm with labels yi.... Bm E 1). Almost surely the are distinct. Define the interpolating classifier f RRd (0,1) as
yi !
if x E (z1,..., 2m
f(x)
(33)
otherwise.
We want to show is robust. Draw (x)... Ia) uniformly on gd-1, There are only two ways a can contribute to the adversarial risk (f.
x is close training sample z; with label noise;
æ is close the "decision boundary" x2 of gd
Hence, remembering Equation
[1
1
RAdv,p(f.Hi p))
( is in a p-ball around least one of the 2:]
+F
2
p
S
2
+
(34)
TP x is in p-ball around at least of the 2:} +P
3i >
p
(35)
15

---

Published as a conference paper at ICLR 2023
By the union bound,
P is in p-ball around least one of the zi]
(36)
S m [|| x
z1
11 S P1
(37)
S m P
|| 2 + ||| 11 - 2xxx, 21) S p²)
(38)
m PP (ar z 1 - /²/22
(39)
As y is rotationally invariant, (a, 21) is distributed the same as Ti. We have proved
/²
Radv, (f. m P 21 2
+
2 P
(40)
We can bound P(x1 2 t] for as follows: let 91,... Da be i.id. standard (0, 1) random
variables.
91
2 t] = IP
2
(4la)
+ 92
TP
[o 2 12 (g)
.... 9
(41b)
1
1
12
91
02
2
+
9d
(41c)
12
d - 1
d -
< PP
P 92 Dd
(41d)
f2
2
where the last inequality is because
implics a 2 c or c.
As 0 1. we can take in both probabilities in Equation chi-square bounds from Lemma in Laurent and Massart (2000).
40
We now use the often-cited
P
2 92
(d - 2 1)s
S exp (-s)
(42a)
P [ot 2 1 1 2s] S exp (-s)
(42h)
Then for 40 sponding probabilities in Equation 442b) and Equation (42a).
d it's easy that both probabilities in Equation
41db less than the corre-
Finally, d goes to infinity,
RAdv, S exp((d/440 + exp(-d/40)
(43)
S exp(-dd/8) + exp(-d/40)) + 0.
(44)
C
POISONING THEOREM
Recall the definition of the adversarial risk RAdv,p from Section 2
RAdv, (fs p) = Parp [e E Bx(x), (*(x) + f(z)))
(45)
For interpolating classifiers with minimal test error, there two sources of adversarial risk: de- cision boundaries and label noise. In this paper, we are specifically interested in the latter. The theorem is casiest to formalize the case where the decision boundary contribution to the adversar- ial risk is negligible. For example, this is the case when the classes are separable with a large margin, or in real-world datasets when there not much data which humans would label ambiguously.
Therefore, instead of working with the adversarial risk, we introduce the separable proxy for the adversarial risk. Let the label noised points S (s1.....SN ) and let f interpolate the training set, and otherwise minimize the test error.
RAdy. (S, (5,1)
def P Pawp EI
<
k N, Sk (x)) S Rfdv.pff:H).
(46)
16

---

Published as a conference paper at ICLR 2023
The proxy adversarial risk R
Poison for the poisoned case is easy to define:
R Poison P.N
sup
Rfdv.p(fs1..... sN7.N)
(47)
$1 S1 &y (supp())
(BB(oL)
sup 8 v Esupp(u)
(48)
k=1
In fact, by compactness argument, the sup above can be replaced by max, but this is not important for the theorem we want to prove.
The uniform version Unif is a random variable. Its value depends on the random training set and which points get their labels flipped. We define it as follows:
Sample training set T random points from je independently, and let S be a random subset of the training set, with each point taken with probability 17. Then
Rnif p.T.n == RAdv,p(S,
(49)
We now ready state our formal theorem.
Theorem 11. Let 1l > be the label noise rate, and let T, m be positive integers representing the training sizes for Uniform and Poisoner. Fix N [ym be be the number of labels the poisoner can flip. For 5 > 0, with probability 5. for any p > O,
1 R p.N
R2po: 2
(50)
for T' = =S mmllog - Iog +) Reiss
To be precise, the Uniform adversary takes at least the following number of samples:
2N
(log N + log 1og
2m
log m + log + log 1 }
T
(51)
Poison T/ P.N
R
Poison P.N
The proof is quite similar in spirit to the proof of Theorem
Proof. Let the Poisoner pick points 81...., 8N Rdd We want prove that with high probability,
Tp. 2 1 (UB((s))
Unif R
We show that, with high probability, a sample of T' points from μ., with uniform label noise with probability will result in many of the balls (sxs having a mislabeled point in them.
Order the points .1,..., 8N such that
(B,(s)) 2 n (B,)
(B,(8N))
(52)
By Lemma 8 with
5. know that there exists K such that
K
N
(
(,s 2
Bp(ss) 1==
1
R
Poison P.N
(53)
2
2
1=1
and μ (B,(s))) Z 1 Poison for all 15k5K. P.N
2N
As in Appendix A we proceed to show that with high probability, random sample of T points from will hit each of the balls B(sk, p) for k < K, because the chosen balls are dense enough to get hit when T 2 m log m. This is enough prove
K (UB,LE)).
Unif 2 P
(54)
A=
since any two points in the same (8)) are within distance 2p of each other.
Let 21,...,27 Zr be random dataset of points from p. We have lemma similar to Lemma T0
17

---

Published as a conference paper at ICLR 2023
Lemma 12. With probability 1 8, each (p((k) for l S K contains mislabeled point z
Proof. We have
P [ E Bp((k)] 2
R
Poison P.N
(55)
2N
and because the label corruption is independent from everything, also have
7
[ (sk) and z, mislabeled]
R
P.N
(56)
2N
Therefore,
P (Bp(5)) mislabeled z; =
(57)
I
II 1=1
P [as & (s(ss) or z; mislabeled]
(58)
7 Puisan
T
(59)
2N
P.N
Tn
< exp
2N
R Poison
P
N
(60)
Here in the last line used + S. et and Equation 51
Now we can use the union bound to prove the lemma:
IP some (5(s)) for S K contains no mislabeled z; 1 K S
(61)
Combining Equation (53) and Equation we have the desired
Unif Tm
Poisson
(62)
As this holds for any 81..... N. and the left-hand-side does not depend on the chosen points S can take the supremum over all possible choices of , to prove the theorem.
D PROOF OF PROPOSITION 6
Proposition 6. Let A < B be integers with A much smaller than B. Let p be mixture model on IR supported on a disjoint union of A + B intervals, such that half of the mass is on the first A intervals and half of the mass is on the last B intervals:
1 Euni Unil (
2B Σ Unif (A+j.A+5+)) 2
1 2A
Let the ground truth label be everywhere. Sample two datasets D1, D2 of size from μ using two different label noise distributions: For Dr. fli the label of each sample x E [0, A B) indepen- dently with probability 11. For DD,, flip the label of each sample probability 2n, and leave the labels of the other samples unchanged. Then, for any p. E (0, 1)) for the number of samples m = (,(A) (ignoring log terms), we have that with probability
[A, B) independently with
For any f which interpolates Dj, the adversarial risk is large: RAdv,p Q2 (1).
There exists f which interpolates Dz, such that RAdv (J.
J.p) (1) O, (4).
18

---

Published as a conference paper at ICLR 2023
Proof. To prove the adversarial risk for D1, simply invoke Theorem Consider the com- pact C U (i, }) The covering number for C is N
2p and its probability mass
(C) =
1. 2 By Theorem for m 2 I&A log
4 p with probability greater than 1 - å we have
that (J, 8. This proves the first part.
For the second part, using Hoeffding's inequality, long as 2 16 (3). we have that with probability least 1-ô, the number of samples in [A, A BJ less than 3m
T Therefore, the number
of mislabeled samples in that interval is also less than 4 with the same probability. Now consider the interpolator that is zero everywhere except at the mislabeled points. The maximum adversarial risk of this interpolator is the probability mass of the union of the intervals [A + j, + 2 each
of the mislabeled points lie in. This probability mass at most 8B
3mp
Setting, m 164 log pd
A
obtain (f Öp (1)
E PROOF OF INDUCTIVE BIAS
Theorem 7. For any p O, there exists distribution μ on R2 and two hypothesis classes H. and F, such that for any label noise rate 11 E (0, and dataset size mn = θ ( in expectation we have that: for all h E H that interpolate Sma.
RAdv, (h. 2 2(1):
(10)
whereas there exists an f E F that interpolates Sm,1 and RAdv.p (fip) =
=0 (p).
Proof. For any p 0, W >> P, construct distribution μ (0, W] {0) follows. Distribute the covariates uniformly randomly in [0, 1 2p, W] and then label then with the ground
truth labelling function f (z) [x1 2 where x [x1, is the two-dimensional covariate.
Next, we construct an dimensional dataset and flip each label independently with probability 1-7. 7. We denote this set with Sm..y-
The hypothesis class FF is the class of one-dimensional thresholds on the first coordinate of the input space (ignores the second coordinate entirely). Define the following interpolating classifier : + {0, 1} follows
- 91 [1 2
if is in Sm..y W1 otherwise
f(x)
As the sampling of the covariates and the label noise are independent events,
Esm., # of mislabeled points in Sm.yl mn.
Then the expected measure the set of points adversarially vulnerable by an adversary pertur- bation magnitude on the classifier h, as defined above, is upper bounded by 2pmnr Using the fact that the total measure of the domain W and that m = θ (t)
we get that
2pmr O(p).
I Smm.n [Rady,p (fip)) S
W
Next, consider the hypothesis class defined follows. Given a of points {21,..., 2 [0, w and p. define the hypothesis
{
3Z E 1 < A 1f2 =
hz,y (x)
3z E 2 2 < p) 1| - 5
otherwise.
If 3 is the of mislabeled is in Sm, then for any interpolating classifier hz it holds that c Z. Next, by construction, for every point z E Z, holds that all points x [a 7, + y] can adversarially perturbed in the 22 component to obtain the label 1. Thus the total measure of the
19

---

Published as a conference paper at ICLR 2023
adversarially vulnerable set of points is greater than the number of mislabeled points, whose original label zero, multipled with 2%y, which is 2m17y.
Thus, have that for any h H. that interpolates Sm...
22ymen
Esm... [Radv,p (fin)] 2 min
2 = (2(7).
We proved the adversarial risk bounds only in expectation over the training set; but note that both of the bounds in Theorem 7 can be transformed into high probability bounds using concentration inequalities.
For simplicity, we did not treat the second bound in the theorem as a learning problem. However, it is possible to show that there exists learning algorithm that uses similar number of samples output E FF such that the adversarial risk is O (p).
F SEPARATION AND AVERAGE DISTANCES OF DIFFERENT CLASSES
For a classification dataset, is not easy to check if given class can be covered by balls of some radius in given metric, such that each ball contains only points from single class.
However, we can estimate the distance distribution between points inside a class and between points of different classes, If those two distributions are similar, and especially if the minimum distances are roughly the same, then it seems likely that it's not possible for the balls to contain only points from single class.
The plots Figure strongly suggest that the points different classes are not extremely "far off" in the I1-112 or Il metrics, compared to the distances between points inside class.
G EXPERIMENTS REGARDING INDUCTIVE BIAS
We show that the the structure of the T-shaped classifier used in Theorem 7 is visible when fitting neural networks label noise on tiny dataset. We sample a three dimensional dataset of points (X, Y, Z) with labels in {0, 1} as follows:
X is sampled uniformly from the segment [0, 1]:
Y is sampled from normal distribution /O00, 0.1); is sampled from normal distribution (0, 0.001);
The label is > 0.5, and otherwise.
We sample 50 points from this distribution to create the clean dataset. To create the noisy dataset, we randomly flip 10% of the labels to generate the noisy dataset.
Then we train one-hidden layer MIP with 1000 hidden units using the ADAM optimizer with learning rate of 0.01. The decision boundary after running this for 350 epochs with batch size of 20 is plotted in Appendix G All our models interpolate the dataset (both clean and noisy).
We plot the decision region the XY plane for three different values of the dimension in Ap- pendix models trained on the noisy dataset well as the clean dataset. The first row in a box corresponds to the model trained on the noisy dataset and the second row corresponds to the model trained on the clean dataset. The maroon circles inside the plots balls of radius 0.04, drawn around the points with label noise, indicating the region of adversarial vulnerability induced by the points in that plane.
As visualizations like these are often susceptible to variance due to random seeds, we report for three different seeds, denoted Run 1, Run 2, and Run 3.
To interpret the T-like structure from Figure 7 in these experiments, note that p = 0.04, so the "head" of the 'T" is in the XY plane for Z 0.04. Further, the 7 -0.04 is essentially the head
20

---

Published as a conference paper at ICLR 2023
Class distances
Class distances
Irisss
Indla
1.00
0.33
0:21
0.02
0/22
distancs
CHUS CROS
distances
Cross
0.01
0412
0.32
0.00
2.4
0.1
0.00
29
0.5
2.5
Clisa distances
Class distances
0:00
0.54
0.22
Ez
Cless distances
Draec
Class distences
Craa--iaa Indlaa
0.10
0.33
0.36
100
0.4
0.5
0.0
0.00
10
20
0.4
0.0
3.0
distances
distences
0.10
0.12
0.02
0.54
0/4
0.5
Figure Separation and average distances of different classes in CIFAR-10.
W
Figure 7: Visualization of a portion of the distribution μ and the hypothesis class H. used Theo-
rem 7 The crosses the mislabeled examples and the circles are correctly labelled examples. All the circles are adversarially vulnerable to upwards perturbations of magnitude less than p.
of the 'T' for the other class. In the first rows in all of the boxes (i.e. the noisy dataset), note that "heads of the Ts" are almost entirely within the decision region of one of the classes. This indicates that all points than 0.04 to change its predicted label, yielding an adversarial risk of 100%. However, in the Z = plane, the region of vulnerability is the union of the maroon balls, which is significantly smaller than what is what induced by perturbation along the Z-dimension. This suggests that our intuition with the T-shaped classifiers may be relevant in practice for neural networks.
the XY plane 2 0 can be perturbed along the Z-axis with perturbation less
21

---

Published as a conference paper at ICLR 2023
2+0044
04
64
9.4
42
-2
12
20
00
Z-0.4
04
64
0.4
-22
<2
-22
80
F2
16
28
92
422
-24
60
2-034
04
CA
0.4
-02
-42
-22
50
02
04
08
1.
08
12
C4
15
1.0
19
92
64
06
18
1.4
0.4
<4
Figure 8: Each box is a different independent sample of the dataset. The first row in each box with label noise, and the second row is without label noise. The three plots in each row (Z e (-0.04, 0.00, 0.04)) show the decision boundary of the interpolating model the XY plane for different values Z. The = 0.04 can be interpreted as the head the 'T' shaped decision region and Z -0.04 is similarly inverted 'T' for the other class. The plots clearly show that when the model interpolates label noise, the width of the head of the 'T's are significantly more responsible for adversarial vulnerability than the decision region in the Z 0 plane.
22


Reviews:
[{"review_id": "x6nyYLLwYwJ", "reviewer": "Reviewer_BXAC", "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": "This paper studies the connection between label noise and adversarial risk by given a theorem on the sample size bound for a given adversarial risk with certain noise rate. This theoretical result improves previous work on sample size lower bound. The author also proves that their theorem is tight under a constructed special circumstance.", "summary_of_the_review": "I think this paper is a good paper to analyze the adversarial risk resulted from label noise and it has a tighter result compared to previous works. But the main theorem is still not enough to explain the cause of adversarial risk completely due to the difficulty in finding optimal C and also its infinite bound when $\\eta = 0$.", "strength_and_weaknesses": "Strength:\n* The paper is written well with clear structure.\n* The theoretical result improves previous works with a tighter training sample size lower bound.\n\nWeaknesses:\n* The tightness of the bound is mostly dependent on the choice of subset C, which is unknown how to get an optimized one.\n* The theorem can not explain the adversarial risk of the model when trained with  clean data where $\\eta = 0$, which requires infinite sample size for a given adversarial risk lower bound.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "tesG08zh86", "reviewer": "Reviewer_BqSH", "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": "Let $S$ be a training set from data distribution $\\mu$ that is labeled by baseline classifier $f^*$ with label noise $\\eta$. This paper investigates the effect that fully interpolating over $S$ has on the adversarial robustness of the resulting classifier (with respect to $(\\mu, f^*)$). They give a highly general result that lower bounds the adversarial loss based on the measure of a compact set, $\\mathcal{C}$, along with the number of balls of radius $\\frac{\\rho}{2}$ needed to cover it. Their result consequently formalizes a simple intuition -- interpolating noise results in classifiers that change their values a lot, and this leads to poor robustness. To complement this, they show that in some cases, their bound on the amount of data needed for this phenomenon to occur is relatively tight.\n\nThey then discuss several implications of their results, including a comparison of the effect of noise with the effect of data poisoning as well a discussion of inductive bias. In all cases, they include a theoretical result (with proof) that gives some sort of lower bound on the robust loss of a classifier that interpolates a noisy training set. They then conclude by conjecturing that a similar phenomenon holds for neural networks, with the necessary sample size being related to the dimension as well as the number of neurons.  ", "summary_of_the_review": "This is a good paper and should be accepted. It studies a simple but interesting problem thoroughly and elegantly. I believe this work is easily understandable and is nevertheless quite non-trivial.", "strength_and_weaknesses": "This paper provides a simple, elegant result that cleanly describes the relationship between interpolating label noise and the resulting robustness. I particularly liked the proof intuition they included in their main body for most of their theoretical results. \n\nI have few comments about this paper. First, I think it would be interesting if they connected this result to some sort of baseline result about the effect that fully interpolating noise has on standard classification. While such a result would probably require some sort of assumption about the hypothesis class being used (my understanding for their result is that by virtue of the nature of robustness, no assumptions are necessary on the classifier), I do think it would still serve for a meaningful comparison.\n\nSecondly, I found their section regarding inductive bias a bit difficult to read. I think including a formal definition of ``inductive bias\", or alternatively defining some sort of related entity would greatly strengthen this section. From my current understanding, it seems as though the reader is expected to connect Theorem 7 to the concept of inductive bias implicitly, and I think making this connection explicit would improve the presentation of this paper.\n\nFinally, I wonder if anything can be said about classifiers that don't fully interpolate the entire dataset, but rather get as close to doing so as possible. In particular, this would describe situations in which the hypothesis class isn't broad enough to achieve 0 loss, but is nevertheless able to significantly overfit to noise. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "lRa0rfqIwqO", "reviewer": "Reviewer_sRSH", "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": "This paper studies the adversarial risk caused by label noise. In particular, Theorem 2 provides a constant lower bound on the adversarial risk of an interpolator in the presence of uniform label noise when the sample size is large enough. Such bound relaxes the assumption and improves over required sample size in the previous results (Sanyal et al., 2021). Eq. (7) and Figure 2 explain Theorem 3 has no control over adversarial risk. Proposition 4 shows that the bound of Theorem 2 is sharp if arbitrary classifiers and distributions are allowed. Theorem 5 considers the game theory perspective and shows if the uniform label noise is given double the adversarial radius and a log factor increase on the training set size, then the risk is as strong as data poisoning. Proposition 6 provides two toy examples of long-tailed data distribution and shows that the interpolating can be benign. Figure 3 shows that uniform label noise is worse for adversarial risk than human-generated label noise. Theorem 7 shows the inductive bias of the function class makes the impact of label noise on adversarial vulnerability much stronger. ", "summary_of_the_review": "This paper improves state-of-art theoretical guarantees and it can be an important advance in the sub-field. Although the theoretical finding does not align with empirical phenomenon perfectly, I still believe the solid analysis and insight outweigh the limitation.", "strength_and_weaknesses": "Strength:\n1. This paper provides stronger guarantee in the same track of work by Sanyal et al. (2021) with weaker assumption. Even though the sample size in the new bound still has a heavy dependence on the covering number but science is incremental. \n2. This paper provides several insightful statements which can benefit future research. Eq (8) and Example highlight potential improvement direction. Conjecture 1 also does the same job with enough literature support.\n\nWeaknesses:\n1. Some toy examples are unrealistic. Firstly, while Proposition 6 argues that some label noise models are benign, I don't believe one can choose what kind of label noise he/she wants as in the toy example.  Secondly, Theorem 7 is based on a constructed hypothesis class with a sequence of T-shaped decision regions, which is hard to image similar shape being produced by real-world dataset and deep networks but the author claims it as \"an illustrative example for what might be happening in practice\". I am also not clear how this setting is related to inductive bias in neural networks.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "g6YHe54SnPT", "reviewer": "Reviewer_HmKE", "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": "The paper studies the adversarial robustness of interpolants (that fit the training data perfectly) in the presence of label noise. They provide bounds on the risk of any interpolant under some mild assumptions on the data generating process. They also prove that adversarial robustness under uniform label noise is close to the worst-case label noise for fixed budget of incorrect labels. They also study the effect of different forms of label noise on real-world datasets and find that \"naturally occuring\" label noise leads to less adversarial susceptibility than uniform label noise. ", "summary_of_the_review": "The paper offers some interesting insights, but is missing a clear overall story or actionable takeaways. I believe the paper is currently borderline and I hope the authors can clarify some concerns raised above that can help tilt away from borderline. ", "strength_and_weaknesses": "Strengths: The paper studies a generally important problem of understanding the robustness of interpolants (like modern deep networks) in the presence of label noise. The result on how uniform label noise is as hard as worst-case noise is surprising and interesting (but might be of limited practical use as discussed below). The paper also performs experiments on real-world label noise (dataset from prior work) and observes that the adversarial risk in the presence of real world human annotator noise is much better than under uniform label noise. \n\nWeaknesses: The first result that generalizes Sanyal's result to more general input distributions does not seem that significant/useful to me. As noted below, the authors should clarify why their assumptions are more reflective of real-world datasets than their current assumptions. I also do not believe this paper offers any actionable insights, apart from possibly the insight that \"real world\" noise is easier to handle than uniform label noise. But of course, there is the difficulty of actually modeling real-world noise correctly. The paper does not compare different training methods (or different interpolants) which seems like an obvious missing piece to me. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "bh4qsw24fxA", "reviewer": "Reviewer_59Qr", "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": "The work studies the relationship between label noise and adversarial risk for interpolating classiﬁers (i.e., classifiers with zero training error). The authors prove that interpolating label noise induces high adversarial risk for any data distribution when the sample size is very large. To better align the undesirable gap between the large sample size required by the theorem and the relatively small sample size of standard datasets, the authors argue that this requires further restrictions/assumptions on the data distribution or the inductive bias of the function class. Additionally, the authors prove that uniform label noise induces nearly as large an adversarial risk as the worst poisoning with the same noise rate, which is of interest on its own.", "summary_of_the_review": "This paper provides a solid contribution to the theoretical understanding of the relationship between adversarial risk, interpolation, and label noise. It would be more impactful if the weaknesses listed above could be addressed well.", "strength_and_weaknesses": "Strengths:\n\n- The first contribution of this work is Theorem 2, which improves the results of Sanyal et al. (2021). Specifically, the authors avoid the unwieldy assumptions from Sanyal et al. (2021) by using a more elegant concept called the covering number.  This not only characterizes data distribution properly but also gives a slightly stronger guarantee.\n- The second contribution of this work is a critical discussion of the required sample size for Theorem 2. In particular, the authors show that the sample size for Theorem 2 is tight in the worst case, while the sample size of standard datasets such as MNIST is much smaller than that required by Theorem 2. Thus, it is not possible to obtain tighter bounds without further assumptions on the data or the model. The authors further demonstrate this point with specific examples.\n- The third contribution of this work is that the authors prove that uniform label noise is on the same order of harmfmul as worst case data poisoning, given a slight increase in dataset size and adversarial radius. This result is pleasant on its own, while the connection between this one and the former two is obscure.\n\nWeaknesses:\n\n- Probably it is not surprising to conclude that label noise increases adversarial error. It is well known that the test error increases with increasing label noise (also shown in Figure 2). Since the adversarial error is an upper bound of the test error, it is natural to conclude that the adversarial error will increase accordingly. \n- Theorem 2 only characterizes the amount of adversarial error, but fails to show why the adversarial error grows faster than the test error. I thought the latter is the most interesting phenomenon shown in Figure 2.\n- Adversarial training is a popular method to minimize adversarial risk. It would be better if the theory can show the relationship between label noise and adversarial risk for adversarially trained classifiers (i.e., classifiers that correctly and robustly interpolate the training set).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "bfUiAEEsQ2I", "reviewer": "Reviewer_eERJ", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "This paper is a follow-up work of Sanyal et al. (2021), who first discovered how label noise and inductive bias of neural networks lead to adversarial vulnerability. The contribution of this paper can be summarized as follows (where I have ordered them according to the importance in my opinion):\n- Theorem 2 improves the result of Sanyal et al. (2021) in case of uniform label noise, providing a lower bound the sample size $m$ required such that with high probability the adversarial risk is $\\Omega(1)$. It relaxed several assumptions in Sanyal et al. (2021) while getting a better bound on $m$.\n- Proposition 4 shows that the bound of Theorem 2 is tight by giving a toy example.\n- Theorem 5 shows that uniform label noise is almost as strong as poisoning, i.e., selecting an arbitrary subset of samples with a fixed size and changing labels of selected samples.\n- Other contributions, including (1) an observation that label noise by human mistake is not as strong as uniform label noise; (2) a hypothesis that label noise for long-tailed samples is very harmful; (3) a toy example as well as a conjecture that the inductive bias of neural networks influences the adversarial risk.", "summary_of_the_review": "On the one hand, the theoretical results of this paper are correct and improve the prior work of Sanyal et al. (2021). The topic of this paper as well as the writing are generally good.\n\nOn the other hand, currently the theoretical contribution seems marginal. Most of these theorems are easy to prove and does not carry much insight. A number of conclusions are made by giving toy examples or by raising as a conjecture, and some are not well-justified.", "strength_and_weaknesses": "**Strength**:\n1. **Writing**: I feel this paper is clearly written. All theorems are easy to understand, and the authors have presented proof sketches for most of them.\n2. **Relevance**: The topic of adversarial robustness is clearly important to the research community, and the authors studied how adversarial vulnerability comes from as well as discussing sample complexity and inductive biases, which can be regarded as fundamental problems in this area.\n3. **Significance**: The bound of Theorem 2 improves prior works, and Proposition 4 shows that it is tight.\n\n**Weaknesses**:\n1. **Limited technical novelty**. I think a major weakness is that most theoretical results in this paper are trivial to some extent. It is obvious that when label noise is present, an interpolating classifier much fit the noise and thus all the neighboring samples must be adversarially vulnerable. In particular, after reading Theorem 2 or Proposition 4, I basically have an idea of what the proofs look like. They did not surprise me or give me much new insight. While this paper indeed improves the bound of Sanyal et al. (2021) who first discovered the relationship between label noise and adversarial robustness, I think tightening the bound of Sanyal et al. (2021) is not a difficult task, so in this respect the contribution of this paper is limited. Note that Sanyal et al. (2021) already pointed out that they ``focused on making conceptually clear statements rather than to get the best possible bounds''.\n2. **Incomplete theoretical results**. A number of results in this paper are either proposed as intuitions or conjectures, or are justified by giving toy examples.\n- The authors demonstrate that if the data distribution is long-tailed and the label noise is more likely to occur in the long tail, then the adversarial risk is large. The intuition is quite easy to understand since a low label noise in regions with high probability mass is already enough to incur high adversarial risk in that region. However, the authors only gave a very toy example (Proposition 6) which is not really convincing to me. I may suggest the authors rigorously define the notion of long-tailed distribution and present a formal theorem.\n- The authors hypothesize that real-world noise is more benign than uniform label noise. However, they did not show why this happen. Moreover, I think it *contradicts the previous argument* that label noise in the long tail is more harmful. The authors wrote that ``in the real world, examples in the long tail, are more likely to be mislabeled''. So why does the adversarial risk become lower according to Figure 3?\n- To show the importance of inductive bias, the authors presented Theorem 7 which is again a toy example. I am not clear how a classifier with a T-shaped boundary relates to practical settings. On the other hand, the setting of Conjecture 1 is general, non-trivial, and important in my opinion, but the authors did not give any justification on why Conjecture 1 may hold.\n3. **Inconsistency with empirical results**. As the authors said, Theorem 2 and Proposition 4 require a prohibitive sample size that does not match the empirical finding. The authors have attributed the reason to the non-uniform label noise and inductive bias. However, the authors did not further derive theoretical results in a proper setting that matches the empirical finding. It is said that ``real-world noise is more benign than uniform label noise'', yet the required sample size is much lower (e.g., on MNIST or CIFAR-10). How can this phenomenon be explained? As for the inductive bias, the author did not give satisfactory results on what inductive bias current neural networks have and how can the inductive bias hurt robustness. If the authors can prove Conjecture 1 (or a weaker version), the quality of this paper can be significantly improved.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "NKG3jLVtYp", "reviewer": "Reviewer_UsFF", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "This submission provides a theoretical result of a lower bound of adversarial risk when data contains noise. Experiments on MNIST and CIFAR10 also demonstrate the correctness of the fact that uniform label noise is more harmful than typical real-world label noise. The authors also show the connection between inductive biases and label noise.", "summary_of_the_review": "In general, I am not familiar with the theoretical parts of this topic. However, I suggest accepting this paper. The results of this paper can provide more insights for researchers working on the area that from label noise and adversarial training. ", "strength_and_weaknesses": "Strength:\n\n1. This paper is very interesting. The authors provide a new adversarial risk when data contains label noise. Theorem 2 is more involved than the results from Sanyal et al. (2021) when the assumption of 'Each ball only contains points from a single class' does not hold.\n\n2. I like Figure 3, it is clear to show that the uniform noise is worst than human-manipulated noise.\n\n3. The motivation of this paper is clear, which is to improve and enhance the theoretical results from Sanyal et al. (2021).\n\nWeaknesses:\n\n1. I expect the authors can provide a section to discuss related works. For example, the work [Zhu, Jianing, et al. (2021)] should be discussed in this submission because it is related to label noise and adversarial training.\n\nZhu, Jianing, et al. \"Understanding the interaction of adversarial training with noisy labels.\" arXiv preprint arXiv:2102.03482 (2021).\n\n2.  I also expect the authors can provide a clear claim about contributions at the end of Section 1, which can make this submission clear. Furthermore, a conclusion section should be added.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "BAdTLKmjDYu", "reviewer": "Reviewer_AQu9", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The paper studies the role of label noise in the data in increasing adversarial risk of the trained classifier. The main theorem gives a constant lower bound on the adversarial risk of an arbitrary  interpolating classifier (one that achieves zero train error) trained on a noisy dataset of sufficiently large size. Subsequently, the authors argue how this result that allows arbitrary interpolating classifiers is weak to explain this phenomenon in practice since it requires very large samples. They give a constructive argument saying that allowing arbitrary interpolators necessarily leads to an exponentially large sample complexity requirement, showing that their theorem is tight. They also show how inductive biases can reduce this sample complexity requirement. Furthermore, the paper explores other noise models other than uniform noise and show that (1) uniform noise is as challenging as data poisoning attacks, (2) long-tail noise is more benign.", "summary_of_the_review": "The paper has interesting ideas about the role of label noise such as the impact of the distribution of noise on the adversarial risk. However, the overall technical significance of the results is unclear to me. The main message of the paper gets lost in the various directions considered here. Therefore, I’m leaning slightly towards rejecting the paper. I would be happy to raise my score if the authors can (1) convince me on the technical novelty of the paper, or (2) explore practical implications of their results.", "strength_and_weaknesses": "**Strengths**:\n- The paper is generally well-written and presents several angles on the underlying problem\n- The discussion and experiments on long-tail label noise were pretty interesting to me, including the use of the memorization score.\n- The authors are honest about the limitations of their theorems and explore potential ways to improve them to bring them closer to practice.\n\n**Weaknesses**:\n- I might be missing something, but I am not completely convinced that Theorem 2 is significantly better than Theorem 1 which is already known. Intuitively, covering number is essentially quantifying the finite set of balls needed to cover the space. In fact, in order to prove Theorem 2, the authors do prove the condition assumed in Theorem 1 with different constants. A discussion on the differences is very important. Furthermore, in the light of Section 3, it is unclear to me as to what the value of Theorem 2 is.\n- The technical contribution is not super clear, and in the attempt to address different aspects of the problem, no particular one is explored deeply.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster