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 paper studied developing robust algorithms in presence of an attacker who can corrupt a portion of the training set in the classical version space learning scenario. In the realizable scenario, the paper provided impossibility result that shows if the attacker can perturb eta fraction of training samples, then the test accuracy cannot be lower than eta*d with high probability, where d is the VC dimension of the hypothesis class. To complement this result, the paper then proposed robust PAC learning algorithms that provably achieve this upper bound, which perfectly closes the robust learning problem in the realizable case. In the agnostic scenario, the paper showed that no algorithms can achieve 2*OPT test accuracy, where OPT is the optimal error rate without poisoning. Then the paper proposed a robust algorithm that achieves O(OPT)+delta error, where delta depends on the VC dimension.
strengths_and_weaknesses: Strengths:

(1). The paper provided a very comprehensive study of PAC learning under data poisoning attacks. When the attacker can corrupt eta fraction of the training set, the paper showed impossibility result and proposed robust PAC learning algorithms that achieve the error lower bound. This result is fundamental as it extends PAC analysis from traditional machine learning to the robust machine learning domain.

(2). The theoretical results developed in this paper is important. The proof techniques are novel and can be used to study related topics in future research. The topic is extremely fundamental in the machine learning community, which help researchers builds deep understanding of data poisoning attacks.

(3). The paper is well-written and the structure is articulated in a very clear way. The annotation goes from realizable scenario to the agnostic scenario, which makes the paper easier to read and understand.

Weaknesses:

(1). I think the threat model studied in this paper is "untargeted data poisoning attack" instead of "targeted poisoning attack". In typical targeted poisoning attack, the goal of the attacker is to change the prediction on a test example to a pre-specified target label. However this paper considered poisoning attacks that aim at reducing the test-time accuracy overall, which is often consider as untargeted poisoning attacks. I suggest the authors check if the terminology is aligned with the SOTA literature.

(2). In the agnostic scenario, while the paper proved that no learners can achieve 2OPT error rate under data poisoning attacks. It's not very clear how the upper bound O(OPT)+delta compares to the lower bound. That said, I am not sure if the upper bound achieved by the proposed robust PAC learner is tight or not. I hope that the authors could elaborate more on this point.
questions: (1). Whether the threat model considered in this paper is targeted or untargeted poisoning attack?

(2). How tight is the error upper bound in the agnostic scenario?
limitations: Yes
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: This work studies the optimal rate of learning for binary settings under a fraction of $\eta$ poisoning data under targeted data poisoning attack. Under realizable setting, the error rate is proportional to $\eta$ and the VC dimension of the hypothesis set, which can be attained by a deterministic learner. Under agnostic setting, for any deterministic learner, a lower bound is present to show an inevitable multiplicative deterioration in the regret.
strengths_and_weaknesses: Strengths:
1. This work shows that under the realizable case the adversarial risk bound is tight in terms of corruption fraction and VC dimension of the hypothesis set.
2. This work provides a lower bound on the adversarial error for agnostic setting.


Weaknesses:
1. I find the poisoning scenario that is described a bit confusing. Notice that targeted poisoning can also be regarded as selecting a targeted label $y_t$, and adding poisoning data to make the test sample misclassify as the targeted label $y_t$. But here to my understanding, the targeted poisoning is the adversary can see the test sample ahead of time so that the adversary can add poisoning data to make the test sample misclassify. 

questions: 1. I’m wondering whether the bound would change if we switch the poisoning attack to non-targeted poisoning attacks. Also, whether there’s any concrete algorithm for the targeted poisoning attack. 

2. For the agnostic cases lower bound, I’m wondering whether considering certain noise settings (i.e. Massart noise, Tsybakov noise) will eliminate the additional multiplicator on OPT.

3. For sec 3.2, I’m wondering whether there’s a lower bound when considering proper learner. 

4. The author has a discussion on the potential role of randomness on page 5, but I think it should be more clear if first put more work into describing deterministic vs randomness in terms of learning rules and models by either giving examples or giving formal definitions. In the middle of the discussion, the author then mixed randomness and improper learning together. I understand the author may express the idea of improper learners like majority vote involves randomness in the model or learning rule, but it’s unclear currently from the text what’s the take-home message.  Moreover, if the learning rule introduces any randomness,  I’m wondering whether there’s any literature studying the scenario where the attacker can also get access to the random seed.

5. For the discussion of prediction stability, I think the author is trying to make a difference between robustness and astuteness, which I suppose has been clarified in [1] before. Though here the context is under data poisoning attack, since the idea is the same, it might be good to make a comparison.

6. In section 4, it'd be helpful to give a formal definition of semi-agnostic learning.

7. In figure 2 PSPV, what’s the definition of $X_{\{h_1,\ldots,h_t\},2k_p}$. Moreover, does PSPV only limited to linear classifiers or there are no constraints on the hypothesis set. Since the only difference between SPV and PSPV is the latter output $h\in\mathcal{H}$, yet both of $h$ are computed via $Maj$, then how can you guarantee the hypothesis computed in PSPV belongs to $\mathcal{H}$?
limitations: Yes.
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 work studies learnability under a targeted poisoning attack.  Specifically, they consider the best achievable error in both the realizable and agnostic settings.  Their method focuses on $\ell_0$ attacks and is fundamentally based on the ensemble-based robustness proposed by Levine and Feizi [2020].
strengths_and_weaknesses: This work follows in a long tradition of learnability under "noise" (defined broadly).   In particular, the authors address several open questions from previous work.  For example, Gao et al. prove a general bound of $o(1)$ but do not consider specific poisoning fractions, e.g., ${\eta = \frac{1}{100}}$.

Overall, I enjoyed reading this paper.  Its organizational structure was clear.  The ordering of the arguments allowed me to easily follow along without having to go back and re-read previous sections. I thought it was well done.
questions: Section 2: Can you clarify what you mean when you wrote "observe that when both the learner and the output model can be randomized, and if the learner is improper, then the whole process of training and testing can be delegated to 'testing time'"?

It is not obvious to me why your method is strictly limited to only the binary classification case.  It seems it should extend to multiclass classification where the difference is w.r.t. to the two most popular classes.  
* Can you comment on this multiclass case and why it seems not to apply?  Was it simply a simplification for the analysis or a technical limitation?

This paper focuses on a single target instance $x$.  Increasingly the focus is shifting to subpopulation attacks [Jagielski et al. 2022] and defenses, where the attacker targets multiple (test instances) and the defender provides certification bounds on multiple instances simultaneously.
* Have you considered how your bounds change under such scenarios?  I understand this question is not the focus of this particular work so "No" is a perfectly acceptable answer.
limitations: The authors do not include a "Limitations" section nor did I expect one for this type of theory paper. 

I would have preferred some intuition in the main paper regarding the origin of the "carefully chosen" subset sizes in Figures 1 and 2.

While the writing overall was clear, the number of typos was a problem, and if this paper is accepted, it needs thorough proofreading.  Some errors are more egregious than others.
* Lines 153 & 155 "Gao et al. Gao et al." as well as "Balcan et al. Balcan et al."
* Line 284: "Besides of Prediction" -- two issues
* Line 32: "ensure the trustworthy of such" 
* Line 339 & 346 regret bound
Line 39: "can can"
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: The paper information-theoretically studies the possibility and impossibility of learning from poisoned data, in a supervised learning setting with deterministic model predictions, against a relatively powerful attacker who knows the data $x$ on which the model will be tested (or deployed). Remarkably, in the realizable setting, they prove matching upper and lower bounds, up to a multiplicative constant. Namely, this error is $\Theta(\eta d)$, where $\eta$ is the fraction of poisoned data and $d$ is the VC dimension of the class of hypotheses.

In the agnostic setting, the paper also provides interesting lower and upper bounds, though the gap is then arguably larger. Namely, they prove that the error is at least (roughly) $2 OPT + \Omega(\eta) - o(1)$, for a large number of training data, while their upper bound only guarantees $\mathcal O(OPT + d \eta)$.

The authors also note that their solution in the realizable setting is not proper (the learned hypothesis aggregates the predictions of several hypotheses). In the specific case of halfspace learning, they propose a construction of a proper hypothesis, but the guarantee is significantly worse ($\mathcal O(\eta d^3)$).
strengths_and_weaknesses: I believe that this paper is an exciting important step towards understanding the possibility and impossibility of learning. So far the literature has only provided guarantees in the case of a vanishing fraction of poisoned data. However, especially in applications like online content moderation, this assumption is very unrealistic. Arguably, as a model gains more users, while it gains more data, it also attracts more malicious users, which may thus represent an increasing fraction of the provided data. Given this, I believe that the paper provides an original and very significant contribution to the important literature on adversarial machine learning.

The paper is well-organized, but there are many typos which make the reading challenging at times. Below is a list of such typos (the list is not exhaustive):
- Line 53: “Due to adversary” => “Due to the adversary”
- Line 58: “even if the adversary knows” => “especially if the adversary knows”
- Line 66: “the Gao et al. [2021]” => “Gao et al. [2021]”
- Line 153: “Gao et al. Gao et al. [2021]” => “Gao et al. [2021]”
- Line 155: “Balcan et al. Balcan et al. [2022]” => “Balcan et al. [2022]”
- Line 156: “under instance targeted” => “under instance targeted attacks”
- Line 161: “Rosenfeld et al. Rosenfeld et al. [2020]” => “Rosenfeld et al. [2020]”
- Line 209: “depend its changes” => “make its changes depend”
- Line 212: “based on adversary’s power” => “based on the adversary’s power”
- Line 216: “In Definition B.1 present” => “In Definition B.1, we present”
Also, the word “semi-agnostic” is not defined in the paper.

Finally, the paper should clarify the difference between what they regard as “targeted attacks”, and what is sometimes known as “model-targeted attacks”, where attackers want a specific target hypothesis to be learned.
- https://proceedings.mlr.press/v139/suya21a.html 
- https://arxiv.org/pdf/2202.08578.pdf (to appear in ICML’22)

EDIT after reading the authors' responses:
The authors' responses were satisfactory to me, which motivated me to increase my rating.

questions: It would also be helpful if the authors could provide actual values for the constants, so that the readers can better understand the gap between the positive and negative results. I have seen that most of these constants are available in the Supplementary Material. I would suggest to add them to the main paper. In particular, could the authors provide the value of $c_2$ in Theorem 4.1? This constant seems especially important, as it is non-vanshing even when $\eta \rightarrow 0$.

As far as I understand, SPV, which has provable guarantees, is also very practical. In particular, it seems to have the same time-complexity as the oracle Lrn which it leverages. Is this the case? If so, I would encourage the authors to mention it in the paper (I fully appreciate the information-theoretical impossibility theorems, but it is even better if the positive theorems are computationally tractable).

It is frustrating that the algorithm used to provide the guarantee of Theorem 4.1 is not described, even informally. Would it be possible to at least provide an intuition of this algorithm?

Additionally, the time complexity of this algorithm is not discussed. Can the authors say a few words about it?

Finally, there have been lower bounds proved for Byzantine heterogeneous learning. How do these relate with the authors' lower bounds?
- https://proceedings.neurips.cc/paper/2021/hash/d2cd33e9c0236a8c2d8bd3fa91ad3acf-Abstract.html
- https://openreview.net/forum?id=jXKKDEi5vJt
- https://arxiv.org/pdf/2202.08578.pdf
limitations: It is a shame that the introduction examples that motivate the paper are unconvincing. It is indeed unclear how and why an adversary would fool autonomous cars into accelerating when shown a stop sign. It is also unclear how a loan applicant could poison a bank’s training set.

I strongly urge the authors to provide much more compelling examples, which I think are numerous. For instance, in content moderation, a troll farm employed by an authoritarian regime or a multinational firm could flag dissents’ and critics’ content on social medias to fool the moderation algorithm into considering that all such critical content should be taken down. As another example, a language model trained on “social media conversations” (like PaLM https://arxiv.org/abs/2204.02311) could be hacked by propaganda and marketing campaigns, who may want the word “meat” to be systematically associated with “delicious” rather than “not environmental-friendly”. Today, the training datasets of such algorithms are arguably full of poisonous attacks (Facebook reports removing 15 billion fake accounts every two years: https://www.techdigest.tv/2021/09/facebook-removes-15-billion-fake-accounts-in-two-years.html).

In particular, the attacker’s knowledge of $x$ can be justified in practice by the fact that, in may use cases where the model is trained on user-generated data, attackers are also users who will interact with the trained algorithm, and provide the values of $x$ that the model will process. This use case belongs to the family of backdoor attacks, which the paper would gain by mentioning.

I believe that the authors should also discuss the role of $d$. Their lower bounds essentially prove that larger models are more vulnerable to adversarial attacks. This is a very important discovery, as it strongly suggests that the race for ever larger models is also leading to significantly more vulnerable models (if we are to believe the paper).
review_title: null

Meta-review: metareview: All reviewers agree that this paper comprehensively studies a fundamental question of PAC learning under instance-targeted poisoning, including the study of realizable, agnostic, deterministic learning settings; overall this paper makes a nice contribution to the field of robust machine learning. 

The authors are strongly encouraged to incorporate the comments by the reviewers, including revising on motivating examples, terminologies, etc. 
confidence: Certain
Decision: Accept