Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work proposes the *Lethal Dose Conjecture* regarding learnability under training-set attacks -- in particular on the amount of data needed by an attacked (sub)model.  The authors demonstrate their conjecture on simple model classes (e.g., instance based-learners).  They also discuss approaches to approve the performance of existing certified defenses generally.
strengths_and_weaknesses: Off the top, there are definitely things I like about this paper; at the same time, I have concerns.  My score is currently set to borderline, and the score changed multiple times over the course of thinking about the paper and writing the review. It is my *a priori* expectation this score will change based on discussions with the authors and other reviewers.

The paper is overall very well-written.  The arguments are laid out clearly.  It uses the right amount of notation to maximize understanding.  Overall, I enjoyed reading it.  I recognize the obvious level of care and thought in the writing.  

I also recognize that there is implicitly some level of courage in writing a conjecture paper and that reviewers should be understanding that even a wrong conjecture can advance science.  Nonetheless, I think the bar for such papers should be quite high, and most conjecture papers may be better suited as a preprint unless especially incisive.  I am not convinced this paper meets that latter bar in particular given related work.

I appreciate the demonstration of the conjecture on simple model classes (e.g., bijective learner, instance-based memorized learner).  There are special properties to those learners that make me concerned of if/how readily the conjecture generalizes.  I understand that the argument is made that the conjecture applies to the two extremes of learnability -- hardest and easiest -- so in theory it applies elsewhere.  I would have hoped had the conjecture been demonstrated on even a simple parametric model class (e.g., a linear model); I also understand that this easier said than achieved.  Overall, I am concerned the claims may be overstated.

I thought the point made in Section 7.3 "*If assuming the conjecture is true, when some defense against data poisoning is clearly more robust than DPA (even in restricted cases), there should be a more data-efficient learner.*" was well-stated and effective.  I think the paper would be improved if that point was made more clearly earlier.
*  As a note, I think there may be a typo at the beginning of that sentence.

I appreciate that the authors consider both DPA and FA.  I think the exposition would be clearer focusing exclusively on DPA and having a statement in the related work about how the arguments made about DPA generalize to FA.  DPA is the older method and the gains from FA are often quite marginal and focused mostly in the tail of the certification bound curve (Wang et al. 2022 Table 1). 
* Granted FA is newer and can lead to improvements at the expense of increased training and inference costs.  I do not think repeatedly mentioning FA here achieves much beyond making FA better known.

questions: In Sec. 7.2, the argument is made that since DPA is asymptotically optimal, then improving robustness "reduces developing stronger defenses to finding more data-efficient learners."
* I understand the origin of this claim, but it seems overbroad.  Could it not also be argued that a better/alternative approach is better ways to determine $\ell_0$ robustness of the individual models beyond the assumption that a single insertion/deletion can arbitrarily change the prediction?
* Under your claim the number of models may need to grow to $n$ which affects inference time efficiency. If there was some way -- say even an oracle -- to quantify the intrinsic robustness of each submodel, would that not be similarly as good?  If not why? 

Assuming the conjecture is true, in what case should an ensemble-based method like DPA be used?  For simplicity of discussion, consider DPA (not FA) with disjoint partitions.
* By partitioning the training set, an attacker with perfect knowledge can ignore $\frac{k}{2}$ of the submodels or in other words about $\frac{1}{2}$ of the training data.  If only $n$ instances are needed to learn the distribution, does this not reduce the best case bound by (about) half specifically if we can certify the robustness of an individual submodel above 1 (as possible with KNN)?
     * In other words, is partitioning merely a way to dilute the effect of "overwhelmingly lethal" instances?
     * I think this distinction and discussion is more and to some degree glossed over in Section 7.
* Granted the claim in your paper is that they are only optimal up to a constant factor and what I describe is a (constant) factor of 2.
* I think clarity on this point is particularly important for me and would improve the paper.

How do your "baseline" experimental results correspond to the published [DPA implementation](https://github.com/alevine0/DPA)?  Does it take out the data augmentation already in the implementation and compare against that?  
limitations: I believe the finding about data efficiency affecting DPA/FA's performance is an obvious one and already known.  Described very briefly, an ensemble's performance sits on top of the performance of its submodels.  If the submodels are made better, the ensemble will improve.  
* For example, without the base augmentation already in [DPA's implementation](https://github.com/alevine0/DPA/blob/ce25c36721f7529350700b071b9a5e1281c31009/FeatureLearningRotNet/dataloader.py#L97), DPA performs much worse.
* I am open to be convinced if others think this finding is less obvious.

Gao et al. [9] study and provides bounds under instance targeted poisoning attack. The relationship of your work to Gao et al. [9] to your work merits a longer discussion than the partial sentence at the end of Section 2.
* As more general feedback, I appreciate when in related work the authors include in the text the author(s)'s names with the citation number. I missed that you even noted Gao et al. the first time I read it because it only had the citation number.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper introduces the Lethal Dose Conjecture (LDC) which speculates on the
minimum amount of bad or poisoned data samples that a learning algorithm can
tolerate (or an attacker can manipulate) before its ability to predict breaks
down. They conjecture that this number is bounded by Θ(N / n) (using "Big
Theta" asymptotic notation) for datasets of size N and problems where a minimum
of n correctly labeled examples are needed. They seek to prove this in three
restricted settings and provide evidence suggesting it may be true in general.

They relate this conjecture to two previously published ensembling techniques
(DFA and FA) that provide robustness when learning on a "poisoned" dataset.
They show that if LDC is true, then DFA and FA are the best mitigations against
poisoned data in the limit as the dataset size grows.

A recurring theme is that data efficiency (the ability to fit a pattern with
fewer examples) is linked to how well a learning algorithm can withstand
poisoning. Experiments use data augmentation to increase the data efficiency of
network-in-network learners on CIFAR-10 and GTSRB.

strengths_and_weaknesses: Please provide a thorough assessment of the strengths and weaknesses of the
paper, touching on each of the following dimensions: originality, quality,
clarity and significance. You can incorporate Markdown and Latex into your
review. See /faq.

The paper is generally well written, well motivated, and provides a good amount
of evidence in support of the claim.

I'm not deeply involved in the related literature on data poisoning, so I can't
comment on how original the work is, but it seems to be a logical (but
non-trivial) next direction given the previous works cited in section 1 and 2.

Apart from having a well-chosen name, the actual conjecture provides a useful
conceptual framework for practitioners to think about data poisoning (or as a
limiting case relating to learning on dirty datasets in general). The N/n
figure makes intuitive sense but nailing it down to exactly that case is
theoretically import.

The code to reproduce the experiments is provided.

I think the biggest weakness is the choice of datasets and experiments.  I
think what is presented is sufficient given the quality of the theoretical
analysis, but I would have liked to see the claim tested against a large
(image-net sized) dataset with a large model, even if the result is: it doesn't
follow the theoretically predicted trend, but that could just be suggesting we
haven't found efficient enough learners.

questions: Please list up and carefully describe any questions and suggestions for the
authors. Think of the things where a response from the author can change your
opinion, clarify a confusion or address a limitation. This can be very
important for a productive rebuttal and discussion phase with the authors.

There are several nitpicks and typos.

Line 33: I find the "by doing nothing" somewhat unclear.

The use of the term "certified robustness" is used several times, but isn't
defined. Adding that definition in the introduction would be helpful. It looks
like line 79 and 80 are getting at the definition, but I think it would be best
to make the term crystal clear.

I'm fairly sure the term "asymptotically" refers to the growth of the dataset,
but that should be stated.

In Figure 1, you forgot a `\` in front of `mu_1`.

In Section 6, (and in the abstract) the upfront claim is that you are verifying
the conjecture in "Gaussian Classification", but upon further reading it is 
more restrictive than that. The Gaussian's have equal co-variance and it seems
that the learning is happening in a balanced setting where each class has
roughly the same number of examples. It isn't clear if the result holds beyond
this case, but the proof seems to specifically address this case. I think this
"balanced equal co-variance" or some other wording to that effect is needed when 
introducing this claim (at least in the list of contributions and in the title
of section 6 or the first sentence).

This also raises the question: What happens in an unbalanced setting? How does
that relate to `n` the minimum number of clean examples needed? When discussing
the number `n` there seems to be a presumption that the minimum number of
examples. I'm not sure if this is worth stating in the paper or not.

In the appendix, I did my best to verify the proofs. Nothing stood out as
obviously wrong, but there were places that I think could benefit from further
explanation (at least for me, perhaps its clear to others).

After line 5, (lets label them 5.1 - 5.5) I don't see how to get from 5.1 to
5.2.

On line 8, it would be more formally correct to say ∈ Θ(k) as Θ represents a
set of functions of which log(2 - 2τ)/log(1 - 2/k) is a member.  This comment
applies elsewhere. This is minor as the intention should be generally
understood, but I wanted to point that out.

On line 19, it wasn't clear to me why `E[| T(D_N) - D_N |] = 2N / k`.

I also marked that I didn't understand steps 46.2 and 46.3.

It may be of some value to put some of these proofs or parts of these proofs
into a proof validator and provide that encoding to provide readers like myself
with marginal theoretical ability to feel more confident about their
correctness.  You could codify difficult to encode arguments as assumptions,
which would mean only the truth of the important concepts would need to be
verified.

I was unable to follow lemma 6 and 7. They would benefit from more explanation.
What is the intuition for taking ε -> 0?


limitations: The authors do not discuss the potential negative impact of this work, but I
think this potential is fringe. In some sense the conjecture could give a
malicious actor a hint on the amount of work they need to do, but it also lets
others know what they need to guard against. I don't think there is any
immediate or zero-day exploit that this enables, so in general I think making
practitioners aware of this (potential) Θ(N / n) relationship is a net social
good.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper suggests a hypothesis for the necessary and sufficient amount of malicious samples needed asymptotically for successful data poisoning. Most notably, the amount is inversely proportional to the minimum amount of data needed to learn the concept for the chose model class. The hypothesis is proven on some learning scenarios. Empirically, it is shown that learning pipelines using more data efficient base learner can achieve higher certified robustness against poisoning.
strengths_and_weaknesses: This paper proposes a wholistic idea with ample theoretical and empirical evidence. The message is clear and thought-provoking. I learned something new. Thank you.

In terms of clarity, this paper is of high quality. The main concepts are mostly clear stated, and the theoretical insights is coupled with intuitive explanation, making it easy to understand by audience with different levels of theoretical background. 

For significance, although the paper is only a hypothesis, the hypothesis statement is thought provoking. The implication to real-world scenario is also impactful: data efficient base learner can achieve higher robustness against poisoning. The empirical evidence further increases the significance.

For originality, the paper stems from previous work of DPA and FA, the angle is new. Whether the hypothesis is eventually proven true or false, the idea is worth presenting to the machine learning community.

Overall, this paper is of high quality. However, I do have a few lingering problem about the strength of the statement, and hope the authors can clarify.
questions: I have two main questions.

1. How should we interpret $n$ --- the minimum amount of data required by the most sample efficient learner? Given a distribution and a model class for the base learner, $n$ would become a constant, wouldn't it? For example, for a linear separable data distribution with margin $\epsilon$, $n$ would just be a constant for a given $\epsilon$. Now, notice the bound is asymptotic, a constant $n$ means the data poisoner always need to poison a constant fraction of the data set. Could you give an example that 1) the model class has a variable $k$, e.g. size of neurons in an NN, 2) $n$ scales with $k$, and 3) the amount of poisoning examples needed has lower order than constant portion given increasing $k$? 

2. Correct me if I'm wrong: the hypothesis suggests that a more complex base learner may be more prone to data poisoning attack. On the other hand, a more complexity model (e.g. deep learning models) has the potential to fit both the poisoning data and the clean data separately, while a simple model (e.g. linear classifier) cannot. How do these two view reconcile with each other? This is out of the scope of the paper, and will not be the ground of my acceptance/rejection. But I'm curious about your opinion. Thanks. 
limitations: The limitations have been adequately addressed.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper suggests a conjecture that quantifies what is the maximal fraction of training data that might be poisoned, while achieving a given required accuracy rate $\epsilon$. Specifically, the conjecture is that roughly $1/n$ of the training data is the maximal poisoned data fraction, where $n$ is the sample complexity of the task, that is, the sample size required to achieve accuracy $\epsilon$ in a "clean" environment (without presence of an adversary). The conjecture is proved for some special cases such as instance memorization. Another theoretical aspect of the paper is a general view of the poisoning problem through distribution discrimination. Practically, the paper summarizes results of some experiments supporting the conjecture: On one hand, robust learners can be derived from data-efficient learners, and on the other hand, data-efficient learners can be derived from robust learners.
strengths_and_weaknesses: Strengths:

1. The conjecture sounds reasonable. The informal arguments as well as the experiments supporting it are quite convincing.
2. The "distribution discrimination" view of the problem is intuitive and insightful.
3. The practical technique of using data augmentation to increase accuracy is interesting and insightful.
4. The idea of deriving data efficient-learners from robust learners is interesting as well.

Weaknesses:
1. The absence of some standard notions in machine learning that seems related to the paper makes the paper and its contribution harder to understand.  For example, it seems that the terms "sample complexity" and "realizability" should have been integrated in the basic definitions. Another example is Lemma 1 which seemingly can be simply proved using the well known VC-dimension, which is not mentioned anywhere in the paper (elaboration in  question 5).
2. The theoretical contribution of the paper is not clear enough to me: The formal statement of the conjecture is not justified enough in my opinion (elaboration in question 2). It is also not explained why the special cases described in Section 4 are interesting, and in what sense they are "easy" or "hard", as written in the paper (see elaboration in questions 4,6). 
3. There are some unclear parts in the text, which also makes it hard to evaluate the paper's contribution. Examples can be found in questions 1,3. 
questions: 1. In the definition of a learner, and poisoned learning: The domain of $T$ and $f$ seems to be defined as infinite vectors where I guess it should be finite vectors?
2. The formulation of the formal statement of the conjecture in page 3 is not justified enough, in my opinion. It seems that the conjecture is formulated with respect to a specific given data point $x_0$. I guess that this what a "specific task" (as written in the introduction) means? However, a "specific task" might be understood as drawing the test point from a *specific* hidden marginal distribution over instances, as usually done in PAC learning. Also, isn't this suggested formulation might be better? For example, think of a point that can only suffer attacks of a very small size, but on the other hand is not likely to be drawn as a test point. Isn't it better to define the lethal dose to be higher, than what reflects in the conjecture, in this case? (because a wrong prediction on this point is not lethal).
3. In definition 1: What does "plausible learners" mean? In what sense are they plausible?
4. The paragraph that comes after definition 1 is not clear to me. What are the "classes" here? In what sense is this setting the easiest?
5. Isn't the proof of Lemma 1 is just by the fact that the VC-dimension of the corresponding hypothesis class is $k$? Just think of the $k$ labels as all possible binary labelings of $\log_2(k)$ data points.
6. The paragraph that comes after definition 2 is not clear to me. Why is this setting so much harder compared with the setting of definition 1? Also, definition 2 seems like a generalization of definition 1, and if that is indeed the case,  perhaps it is good to mention that.
limitations: Yes, except for what is written in question 2 about the formulation of the conjecture.
review_title: null

Meta-review: metareview: The reviewers agree that this work proposes an interesting conjecture which is likely to inspire further research.
Congrats!

During the discussion period the following two points were raised by the reviewers:

- The paper should emphasize more strongly that this is just a conjecture (I at minimum have doubts have how well it generalizes). They should make clearer the alternate hypotheses/explanations in the main paper and discuss them.
- Nascent researchers look at archived OpenReview discussions and may adopt similar styles as successful authors. I do not think the authors' approach of ending every post with a plea to increase the score is an appropriate or healthy style for peer review. I further advocate it definitely should not be emulated/copied. If reviewers believe scores should be raised (as I did), they should be trusted to do so without pressure from authors.


confidence: Certain
Decision: Accept