Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
strength_and_weaknesses: Strength:
* The paper is written well with clear structure.
* The theoretical result improves previous works with a tighter training sample size lower bound.

Weaknesses:
* The tightness of the bound is mostly dependent on the choice of subset C, which is unknown how to get an optimized one.
* 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.
clarity,_quality,_novelty_and_reproducibility: The paper is written clear and has improved the previous work with a tighter provable bound.
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$.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 
strength_and_weaknesses: Strength:
1. 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. 
2. 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.

Weaknesses:
1. 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.
clarity,_quality,_novelty_and_reproducibility: Clarity wise is good. While this paper focuses of theoretical justification, it is still easy for experienced reader to follow since the author provides proof sketch to every theorem and proposition. Meanwhile the discussion with respect to related work makes the contribution more solid. Toy examples also provide convincing insight. Some improvement can be done. Please see Strength And Weaknesses. 
Originality and quality wise are also good. Although this paper borrows some idea on toy examples, the main theorem include non-trivial technique in its analysis. To my knowledge, these results are both novel and insightful in the subfield of adversarial robustness. 
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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):
- 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$.
- Proposition 4 shows that the bound of Theorem 2 is tight by giving a toy example.
- 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.
- 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.
strength_and_weaknesses: **Strength**:
1. **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.
2. **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.
3. **Significance**: The bound of Theorem 2 improves prior works, and Proposition 4 shows that it is tight.

**Weaknesses**:
1. **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''.
2. **Incomplete theoretical results**. A number of results in this paper are either proposed as intuitions or conjectures, or are justified by giving toy examples.
- 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.
- 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?
- 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.
3. **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.
clarity,_quality,_novelty_and_reproducibility: See the section above. 
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.

On 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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 
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. 

Weaknesses: 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. 
clarity,_quality,_novelty_and_reproducibility: Clarity: At a local level, the paper is quite clear and easy to follow. However, I was unfortunately struggling to get a big picture and unified view on the results. Section 3 was particularly confusing and did not add to the flow of the rest of the paper, which already felt like a combination of disjoint pieces. 

(Major) 
i. Could the authors please clarify why the assumption of Sanyal et al. about input distribution consisting of balls with a single class is unrealistic? It seems like an assumption on the separation between classes which seems natural.  

(Minor)
(a) In the introduction, it is not clear how this work relates to Sanyal et al. What is natural vs adversarial vs uniform random label noise? It needs to be motivated 
(b) the presentation didn't make it very clear that $f$ is any interpolant. The definition was buried in the setup 

Quality: The theoretical results are generally precise and look accurate (I didn't verify all proofs), and the experimental conclusions are well substantiated. The paper makes a series of conjectures that seem a little unnecessary, and it was hard to get clear takeaways from those parts. The paper mentions inductive biases, but offers no real-world "obvious" experiments like comparing interpolants obtained via adversarial training to interpolants obtained via ERM. 

Originality: The paper builds heavily off of the work of Sanyal et al., and extends their results to more general settings. Experiments on different kinds of label noise seem novel and interesting. 
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
strength_and_weaknesses: Strengths:

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

Weaknesses:

- 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. 
- 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.
- 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).
clarity,_quality,_novelty_and_reproducibility: The paper is clearly written and the quality is good.
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
strength_and_weaknesses: **Strengths**:
- The paper is generally well-written and presents several angles on the underlying problem
- The discussion and experiments on long-tail label noise were pretty interesting to me, including the use of the memorization score.
- The authors are honest about the limitations of their theorems and explore potential ways to improve them to bring them closer to practice.

**Weaknesses**:
- 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.
- The technical contribution is not super clear, and in the attempt to address different aspects of the problem, no particular one is explored deeply.
clarity,_quality,_novelty_and_reproducibility: The paper is generally well-written, and seems reproducible from the proofs. There are novel ideas in the paper, but some seem to be incremental. Here are some points on improving the exposition:
- In the theorem statements, it would be helpful to remind what $f$ is.
- In Fig 2, ensure that the labels are not covering the plots
- A conclusion section would greatly help the paper to condense the key takeaways.
- The bar chart is a little confusing, would be good to plot the two with their averages and standard deviations (box and whisker plot).
- Define $\mathcal{H}$ & $\mathcal{F}$ in Theorem 7
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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.

They 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.  
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. 

I 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.

Secondly, 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.

Finally, 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. 
clarity,_quality,_novelty_and_reproducibility: Quality: their work consider an interesting problem -- understanding the role that fully interpolating data with label noise has on adversarial robustness. Their work is theoretically sound and even has practical significance considering the well known phenomenon of overfitting using deep neural networks. 

Novelty: to my knowledge, these results are novel and include a significant improvement over previous work in this area. They include a comparison to older work, and I believe that their results are much more compelling and elegant. 

Clarity: their work is well written -- their theorem statements and proof ideas are all easy and natural to follow. My only negative comment is addressed above where I claim that this paper could improve from a better explanation of "inductive bias."
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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.
strength_and_weaknesses: Strength:

1. 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.

2. I like Figure 3, it is clear to show that the uniform noise is worst than human-manipulated noise.

3. The motivation of this paper is clear, which is to improve and enhance the theoretical results from Sanyal et al. (2021).

Weaknesses:

1. 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.

Zhu, Jianing, et al. "Understanding the interaction of adversarial training with noisy labels." arXiv preprint arXiv:2102.03482 (2021).

2.  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.
clarity,_quality,_novelty_and_reproducibility: In fact, I do not fully check the proofs. However, the theoretical results from this submission are novel. This submission should be polished, especially the contributions and conclusion.  

The authors do not provide code. Thus the reproducibility cannot be verified. Especially the reproduction of Figure 3-related experiments.  
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.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Summary
---
This paper studies the relationship between label noise and adversarial risk. The authors prove a theorem showing that interpolating label noise can lead to adversarial vulnerability, and demonstrate that this result is almost tight when no assumptions are made on the inductive bias of the learning algorithm. They also investigate how different factors, including the properties of the data distribution, impact this result. They show that uniform label noise can lead to nearly as large an adversarial risk as worst data poisoning, and provide both theoretical and empirical evidence that real-world label noise is less harmful than uniform label noise. Finally, they demonstrate that inductive biases can amplify the effect of label noise.

Strengths
---
- Theorem 2 improves upon previous work and has a tighter training sample size lower bound.
- It shows that uniform label noise can be nearly as harmful as worst case data poisoning, given a slight increase in dataset size and adversarial radius. It also performs experiments on real-world label noise and observes that human-generated label noise leads to less adversarial susceptibility than uniform label noise.
- It provides insights on the impact of different forms of label noise and inductive bias on adversarial vulnerability.
- It is well-written and presents clear intuition for its theoretical results. It also explores potential ways to improve the results to bring them closer to practical use.

Weakness
---
- The tightness of the bound for Theorem 2 may not be practical for standard datasets. The theorem also does not provide a bound for the adversarial risk of a model trained with clean data ($\eta=0$), which requires an infinite sample size for a given adversarial risk lower bound. The authors acknowledged this point in their response. 
- As the authors honestly admit, there are limitations of the authors' theorems and they explore potential ways to improve them to bring them closer to practice.


justification_for_why_not_higher_score: - As the authors honestly admit, there are limitations of the authors' theorems and they explore potential ways to improve them to bring them closer to practice.
justification_for_why_not_lower_score: - The paper provides several interesting insights, for example, 
  -  human-generated label noise leads to less adversarial susceptibility than uniform label noise.
  - uniform label noise can be nearly as harmful as worst-case data poisoning
- The main result (Theorem 2) improves upon previous work and is shown to be tight
Decision: Accept: poster