Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors propose a theoretical study on the robustness of binary classifiers against backdoors. To this end, they provide a theoretical framework and define a measure to assess classifiers' memorization capacity. This formulation allows the authors to demonstrate the existence of backdoors in some settings and explain why adversarial training reduces the vulnerability to backdoors. 
main_review: The main contribution of this work is the framework devised by the authors to explain some aspects underlying the success or failure of backdoor attacks. While related work in the area of backdoor attacks is well acknowledged and discussed, the authors should better position this work also with respect to other theoretical analyses related to the memorization of training samples and to the relationship between over-parameterized models and their ability to fit random labels. In particular, from this manuscript, the memorization of the training points seems a concept discovered and defined by the authors. However, this is not the case, as previous work has defined this concept [a] and provided a way to estimate training point memorization [b]. The authors should also clarify that it is already known that robust training increases the robustness against backdoors [c]. 
Last but not least, it would be really a plus if the authors could somewhat connect their work to these papers:
- https://arxiv.org/abs/1611.03530,
- https://arxiv.org/abs/2105.14368 (Sect. 5.2 and reference [10]).

Notwithstanding, this manuscript has some novelty. To my knowledge, the concept of memorization capacity has never been related before to the vulnerability against backdoors, and the validity of adversarial training as a defense against this attack was empirically shown but not theoretically explained. The formulation devised by the authors may be adapted in the future to understand better other phenomena related to machine learning robustness against attacks. 

I appreciated the authors' effort to explain the proposed formulation clearly. To be a theoretical paper is pleasant to read and easy to understand, even though a bit dense in some parts. I would also recommend the authors to try to better emphasize and recap (e.g., in the conclusions) constructive ways in which their formulation can be adopted to improve current algorithms/best practices.

Overall, I think this work provides a fair contribution to the state of the art.

Minor comments:

As a minor comment, the first work introducing backdoor attacks is not [6] but:
- T. Gu, B. Dolan-Gavitt, and S. Garg. Badnets: Identifying vulnerabilities in the machine learning model supply chain. In NIPS Workshop on Machine Learning and Computer Security, abs/1708.06733, 2017.


References

a) Arpit, Devansh, Stanisław Jastrzębski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S. Kanwal, Tegan Maharaj, et al. ‘A Closer Look at Memorization in Deep Networks’. In Proceedings of the 34th International Conference on Machine Learning - Volume 70, 233–42. ICML'177. Sydney, NSW, Australia: JMLR.org, 2017.

b) Feldman, Vitaly, and Chiyuan Zhang." What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation". In Advances in Neural Information Processing Systems, edited by H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, 33:2881–91. Curran Associates, Inc., 2020. https://proceedings.neurips.cc/paper/2020/file/1e14bfe2714193e7af5abc64ecbd6b46-Paper.pdf.

c) Borgnia, Eitan, Valeriia Cherepanova, Liam Fowl, Amin Ghiasi, Jonas Geiping, Micah Goldblum, Tom Goldstein, and Arjun Gupta. 'Strong Data Augmentation Sanitizes Poisoning and Backdoor Attacks Without an Accuracy Tradeoff'. ArXiv:2011.09527 [Cs], 18 November 2020. http://arxiv.org/abs/2011.09527.

limitations_and_societal_impact: Potentially-negative societal impact and limitations have been discussed.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This work proposes a theoretical framework to draw connections between several phenomena in machine learning observed empirically but never adequately understood- the relationship between excess model capacity, perturbation robustness, and backdoor poisoning. They show how under specific settings, adversarial training can detect backdoored data or recover a classifier robust to the backdoors at the very least. Similarly, they show how learning a backdoor-robust classifier is equivalent to pruning corrupted train data. They further demonstrate the applicability of their theorems on the MNIST dataset.
main_review: ## Positive Feedback

1. This work has instrumental theoretical contributions: in terms of findings, theorems, the framework itself, and equivalence between robustness and susceptibility to poisoning.

2. Problem 2  has been formulated well, with an easy-to-follow breakdown of the adversary's goals. Having equivalent text explanations next to formulae is very helpful. 

3. The fact that results from the proposed framework align with empirical observations in this field by other authors reinforce this work's soundness and helps better understand the reason behind those phenomena. 

---

## Criticism

1. Empirical results help show that the proposed theory extends to implementation (which can sometimes lead to significant drops because of stochasticity in model training and constants in equations). Given that the authors did perform such experiments (Supplementary material), it would be great to have a small sub-section summarizing those empirical results.

2. Line 208: "..a 0-loss classifier" . Would this result hold if the focus were to find some $\epsilon$-loss classifier for some reasonably small $\epsilon$? I am a bit concerned about this part since, in a realistic training scenario, the model training would rarely find a 0-loss set of parameters (and even if it could, would never want 0 loss on training data).

---

## Minor comments

1. Line 1: "...supervised learning" is not a requirement for backdoor data poisoning - the setting can also be unsupervised or semi-supervised. Lines 1-7: Do not need such an extended portion (that too in the abstract) dedicated to this definition. In general, the Abstract could use a rewrite - it is too long right now and captures unnecessary details.

2. Lines 26-28: can skip, is pretty common knowledge in this field by now.

3. Line 3: "...(nearly) 0 error" not sure I agree with this - wouldn't having a training error too low be akin to overfitting, which is something machine-learning algorithms actively avoid.

4. Section 1.2: It is nice to see that the authors include this, but it would probably be best to shift it to later in the paper.

5. Theorem 17 uses $\alpha\leq\frac{1}{3}$ and Theorem 18 uses $\alpha\leq\frac{1}{6}$. My understanding is that the $2\alpha$ fraction from Theorem 18 connects to Theorem 17? If yes, it might be worthwhile to write them accordingly before combing the two Equations to imply equivalence because, at the moment, both Equations have different constraints.


## Update

Increased confidence to 4
limitations_and_societal_impact: The authors could certainly extend their empirical evaluation to more complex datasets in the near future. Still, I do not see any obvious limitations in its current state except the ones already stated in their assumptions. Nonetheless, it would be interesting how this could be utilized to perform "adversarial training" indirectly - especially for text-related tasks.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper gives a variety of backdoor-related theoretical results. In particular it, 
1. gives a theoretical framework for discussing backdoor poisoning attacks,
2. shows that the attacker does not need to know the true data distribution to launch an attack against an ERM learner,
3. introduces _memorization capacity_, which measures the amount of off-distribution data a learner can memorize, and shows that nonzero memorization capacity is both necessary and sufficient for the existence of a backdoor attack
4. (the attack constructed in 4. can succeed with limited poisoned data regardless of how much clean data there is),
5. under assumption of finite VC-dimension, shows that adversarial training can be used to detect backdoor attacks, and
6. under the same assumption, shows that the problem of learning a backdoor-resistant model is equivalent to the problem of filtering poisoned data from the dataset.

main_review: The paper multiple noteworthy theoretical results relating to backdoor poisoning attacks. 

Typos:
287: Assumption on VC-dimension is incomplete.

limitations_and_societal_impact: They have.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper offers a theoretical framework to analyze and understand backdoor attacks. They define a notion of memorization capacity to characterize vulnerability of the learning problem to backdoor attacks. Under this framework they give examples of learning problems where explicit backdoors can be constructed easily and problems which are intrinsically robust to backdoors. Further, they also show that under certain assumptions, backdoor filtering and robust generalization are nearly equivalent. Which suggests, it is sufficient to design backdoor filtering algorithms. 
main_review: Recently, lots of works have shown vulnerability of deep neural networks to backdoor attacks. However most of these works have been empirical in nature and based on designing/ detecting the attack and proper theoretical understanding of backdoor attacks is lacking. This paper tries to fill this gap by offering a nice theoretical framework to understand whether the given learning setting is vulnerable to backdoor attacks or not and how we can understand it quantitatively. Their notion of memorization capacity and results are definitely valuable in this context.  Although they have nice set of results, I find this paper lacking in clarity. Intuitions and proof sketches are expected at least for the main theorems in the main paper. It would have been better, if the paper elaborated more on the connection between excess capacity and vulnerability to backdoors. 
limitations_and_societal_impact: One key limitation is the current work is focused heavily on overparameterized linear classifiers, which are a good starting point. Would have been nice to generalize these results to non-linear/ deep net classifiers.
review_title: null

Meta-review: All reviewers agree that this is an important result filling in the gap of theoretically understanding backdoor attacks. 
Decision: Accept (Spotlight)