Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 3: Clear rejection
review_content: summary: This paper studies the "data-oblivious poisoning attack," which presumes an adversary without the knowledge of the victim's training set. Once the authors define the threat model of an oblivious attack, they formulate the security game where an adversary crafts poison samples and a victim trains classifiers on the contaminated training set. Under this formulation, the authors compare the power of a full-knowledge attacker with that of the "oblivious attack." In there, the authors show that oblivious attackers are weaker than full-knowledge attackers. In evaluation, the authors demonstrated that the number of poison samples requires to cause the same deviation of a specific feature becomes larger in "oblivious" attacks.

main_review: **I reviewed this paper in NeurIPS 2020. I compare the two submissions (this one and the previous one) and found that the major concerns that I raised in the review have not been resolved yet. Therefore, I am leaning toward rejecting this paper. I also shared the detailed comments below.**

----
**[Major concerns]**


As this paper presents a new attack, "data-oblivious adversary," I look at this paper as offensive research. On the offensive side, I evaluate the paper with two criteria:

(1) Does this paper help us to understand the unknown worst-case attacker?
(2) Does it provide fundamental insights in building defenses against an attack?

Unfortunately, I don't think this paper still serves any of those purposes. The conclusions are:

(1) The paper studied a weaker poisoning attack and found that the attack is weak.
(2) The authors argue that, since the attack is weak, we are safe as long as the data is not shared with the adversary.

We already know (1), I am not sure whether (2) is true, and the claim is only provable in LASSO (Line 66).

So, there is no addition to the knowledge that prior work found.


--------
**[My lasting concerns]**

In the previous review, I examined this paper with the following three dimensions:


**(1) Is the research question well-motivated?**

I am still super-confused about why we need to consider the "data-oblivious poisoning" attack.

Firstly, I am not sure it has research value. Recall that there has been a vast literature on the full-knowledge poisoning attacks, and we know what would be the worst-case consequences of data poisoning attacks and the defenses on that (e.g., in [1,2]). Then, I couldn't find the reason we should consider any sub-optimal poisoning attacks. If a defense can defeat the strong attacks, it can, of course, work for the "oblivious attackers". Even the experimental results in this paper also reached the same conclusion --- an oblivious attacker is weaker than the full-knowledge attacker.

Secondly, the assumption---an adversary may not know the training samples---itself is under-specified and could be incorrect as there are millions of easy ways an adversary approximates the statistics of a victim's training set. The fundamental assumption in ML is that the training and the testing samples are drawn from an underlying data distribution (using i.i.d sampling mechanism); thus, an attacker can exploit this. For example, one can train a surrogate model on samples crawled from public sources to estimate the impact of an attack on the actual victim model, which has been shown as "transferable poisoning attacks" in vast literature.

**[New]** For the second point, the authors provide some motivating scenarios, e.g., when multiple parties compute a neural network. However, I am not sure those scenarios guarantee "data-obliviousness." As long as the attacker has access to a model, they can extract the training samples and conduct much stronger poisoning attacks.


**(2) Does this paper have clear, novel contributions?**

I am still sure that the contribution is not clear and weak.

**[New]** This paper claims that "we provide theoretical evidence that obliviousness of attackers to the training data can indeed help robustness against poisoning attacks." I do not think that this is a contribution. In the paper, I cannot find any content that proves robustness against poisoning attacks. For example, I cannot find any metric that I can formally measure the robustness.

Secondly, it's the same question that I asked in (1). Why do we need to know how much stronger full-information attackers are? Based on the poisoning literature, I assume the purpose is to know the limit of a poisoning attacker so that we can come up with accountable defense mechanisms against those strong attacks. But, as the authors already show the oblivious poisoning is already weaker, I can't see the benefits of knowing oblivious poisoning attacks.

**[New]** The paper still contains a lot of under-specified terms such as "close training set" (how do you measure this similarity) or "information complexity" (how do you formally define this complexity?). The authors should clearly define them before developing further theoretical claims. Currently, the paper shoots vague terms in the introduction and related work and develops a theory in the following sections.

limitations_and_societal_impact: I could not find this in the manuscript.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies the difference between data-oblivious and data-aware adversaries in ML. In particular, the authors present a result about the effectiveness of such adversaries against feature selection with LASSO and show that the data-aware adversary is provably stronger in such a scenario. Experiments on synthetic and real data suggest that such a separation is also of practical importance.
main_review: $\textbf{Originality}$

The presented results are, to my awareness, novel. The proof technique appears interesting and potentially transferable to other learning setups. The related work is covered very well.

A suggestion regarding the related work is to include a discussion on different adversaries in the context of mean estimation and PAC learning. For mean estimation, the relation between the classic Huber contamination model [1] to the adversarial model of [2] is somewhat similar to the relation between the adversaries discussed in the paper. For PAC learning, [3] and [4] give formal definitions of two data-aware adversaries.

$\textbf{Quality}$

The work appears technically sound and the main results are presented in full rigor within the main body of the paper. A good amount of intuition about the proofs is presented, with full proofs included in the supplementary material.

$\textbf{Clarity}$

Overall, the paper is well-written and easy to follow, with various discussions helping the readers to gain more understanding. Some suggestions for improvement are as follows:

- Abstract: "devastating" is a strange word to use here, perhaps "harmful" or "effective"?
- I found the third paragraph of section 2 a bit hard to follow: perhaps it's helpful to make a difference between the goal of a poisoning attack from how it is done a bit earlier in the paper.
- Definitions 3.3 and 3.4 have an implicit dependence on $n$, the size of the clean dataset. Perhaps you should talk about $(n,k, \delta)$-resilient distributions.
- Figure 1(a), caption: average number of *points*, not *features*? 
- Page 8, last paragraph: the results are shown in Figure 2, not 3. Also, why are the results for MNIST in the synthetic data plot, rather than with TOX and SMK? If it's for space reasons, it would be good to fix this for a potential camera-ready version.
 

$\textbf{Significance}$

Studying the robustness of various ML algorithms to different adversaries is certainly of great current interest. The results presented in the paper only focus on the robustness of a fixed algorithm, LASSO. Nevertheless, the authors show a provable separation between two adversarial models, which I find interesting. Furthermore, the technique could be applicable to other learning setups, so the paper could be a first step towards more general separation results.

$\textbf{Summary}$

The paper is well-motivated, well-written and well-executed. While the results only hold for one fixed learning algorithm, I find this an interesting first steps towards more general results and therefore I think that the paper will be relevant for the NeurIPS community.


$\textbf{References}$

[1] P. J. Huber. Robust Estimation of a Location Parameter. In: The Annals of Mathematical Statistics, 1964.

[2] I. Diakonikolas et al. Robust estimators in high-dimensions without the computational intractability. In: SIAM Journal on Computing, 2019.

[3] M. Kearns and M. Li. Learning in the presence of malicious errors. In: SIAM Journal on Computing, 1993.

[4] N. H. Bshouty, N. Eiron, E. Kushilevitz. PAC learning with nasty noise. In: Theoretical Computer Science, 2002.
limitations_and_societal_impact: I find no serious issues in this regard.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper raises the need for separating the notions of data-oblivious poisoning attacks from data-aware poisoning attacks. Theoretical analysis on feature selection with LASSO show that data-aware adversaries are provably more devastating compared to data-oblivious adversaries. Empirical results on synthetic and real-world datasets also verify the arguments.
main_review: ### **Originality**

The paper deals with the impact of keeping the training data secret from adversaries, while letting the attackers fully know the data distribution. This scenario is relatively realistic and has rarely been studied before.

### **Quality**

Main claims are theoretically supported for the case of feature selection with LASSO under the Gaussian setting. Experimental results validate the theoretical implications both on synthetic datasets sampled from Gaussian distributions and several real-world datasets.

### **Clarity**

The paper is clearly written and well organized. Line 317: "feature" -> "feature."

### **Significance**

The separation result provided by the paper has several implications, including the possibility of designing new defenses for data-oblivious poisoning and the new motive for privacy, which I personally appreciate. 

However, the theoretical results only work for the case of feature selection with LASSO. It's still unclear whether the situation holds for the general classification and regression problems. Deriving theoretical or experimental results on these problems would further broaden the impact of this paper.

Nevertheless, the paper gives a solid theoretical case for the separation result, and brings implications for designing defense mechanisms that leverage the secrecy of training data. I think it's meaningful for many applications such as the scenario of cryptographically secure multi-party protocols for neural network training.

Overall, I’m on the border for this paper. I would be happy to adjust my rating based on the discussion and revision.
limitations_and_societal_impact: The authors may need to discuss how the results for the case of feature selection with LASSO generalize to more general machine learning problems such as classification and regression.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper studies the (information-theoretic) power of an adversary in poisoning attacks. The authors exhibit a learning model (feature selection with Lasso) in which an adversary that has knowledge of the training set is provably stronger than an adversary that has no knowledge of the training set. (In both cases the adversary also has access to the distribution of the data.) The authors complement their theoretical findings with experiments on both synthetic and real data.

To show their theoretical result, the authors define the notion of unstable and resilient distributions under addition of poisoned data to the original dataset. They show that Gaussian distributions with suitable parameters are both resilient and unstable. This means (acc. to Prop 3.5) that data-aware adversaries can profit from the instability of the distribution to create poisoned data that cause Lasso to incorrectly select certain features with high probability, while the distribution's resiliency ensures that data-oblivious adversaries have to create attacks at random.
main_review: ## Review

This works seems to be a solid contribution to learning theory, as it provides a novel result, is well-motivated, and is presented in a neat and organized way. The paper is very well written and clearly organized. The discussion on the relation to prior work is thorough and very clear. 

I believe this paper would open up the avenue for future work on information-theoretic separation results for poisoning attack in other learning settings (e.g. classification), with more general assumptions in the feature selection setting (e.g. no restriction on the learning algorithm, compared to the explicit Lasso algorithm in this work) or to further the theoretical understanding of experimental results (i.e. how the partial access to the training dataset changes the guarantees). 

I think lines 97-99 highlight the compelling nature of the result: even given full knowledge of the data distribution, having access to the training data give vastly different robustness guarantees.


## Questions

The claims and method seem correct to me, though I have a couple of questions:

1. Instability is characterized by the existence of a coordinate i that is not picked up on by Lasso on the clean data, but that is selected on the poisoned data -- this omits the case where i is selected on the clean data but not on the poisoned data. Is there a reason for this?

2. Distribution of the data (l.223-227): what happens if the data is nowhere near the region [-1,1]^d? Referring to the experimental setup, the real-world data was centred and normalized -- is the training data assumed to be centred and normalized in the theoretical results as well? If the data is very far away from the origin, it seems that adding points in the region [-1,1]^d could have the same effect that poisoning the dataset with points far from [-1,1]^d would do in case the data is indeed centred and normalized (i.e. "playing the role of a large dataset" as the authors mention on line 227).

## Suggestions and comments

Math typos/suggestions:
* l. 245: should be the size |.| of Supp()
* l. 246: introduce the lambda parameter formally, and perhaps index theta with lambda (as done in definition 3.2)
* Theorem 3.1: It would be good if the dependence of n,d and sigma on k and the epsilons were stated explicitly to give an idea of how large the dataset and input dimensions need to be to have the result.

Suggestions:
- l.31-32: It would be good to highlight the main reasons why poisoning attacks have been identified as "the most important threat model" in the survey (instead of basing the claim on the survey's "authority")
- l.148: the parameter theta hasn't been introduced at this point -- please use words instead or define it
- l.213: I think it would be better to write out the steps explicitly 

English style/grammar comments & suggestions:
- l.28: "difference usually measured" -> "the difference is usually measured" (full sentence)
- l.90-91: "Doing so... models" -> I think this sentence is unnecessary 
- l.147: "the question of whether adversary" -> "the question of whether the adversary"
- l.148: "adds another dimension of adaptivity to the story" -> weird formulation? maybe change to ""
- l.155-156: "The focus of this work is mostly on the feature selection as one of the important tasks in machine learning." unclear formulation, and I think ranking machine learning tasks is a bit unnecessary. Perhaps something like "This work focuses on feature selection, which is a significant task in machine learning." would be better?
- l.181 "...}, we denote the set of (indices of) its non-zero coordinates of $\theta\in R^d." -> "...} to denote the set of (indices of) its non-zero coordinates."
- l.196 "data data-oblivious" -> "data-oblivious"; probably better to break the sentence in two after "an adversary A"
- l.197 "by adversary's budget" -> "by the adversary's budget"
- l.202 "such that each row and" -> incomplete sentence
- l.214 "feature flipping attack" -> "feature-flipping attack"
- l.244 "theta* where number" -> "theta*, where the number"
- l.245 "are bounded" -> "is bounded"
- l.246 remove hat from theta^*; add a period; "by optimizing the a" -> "by optimizing the"
- l.251 "the robust version, considers" -> "the robust version considers"
- l.272 "Bellow" -> "Below" 
- Defn 3.2: It took me a while to parse the sentence "if its i-th coordinate of model learn on it is 0", perhaps something like "the i-th coordinate of the feature vector obtained by running Lasso on [X | Y] is 0" would be better.
- l.287 "Gaussian distribution" -> "Gaussian distributions"
- l.290-291 "We first show that each feature in the Gaussian sampling process the probability of the i-th feature being k-unstable is proportional to $e^{\lambda - k}$" -> "We first show that each feature in the Gaussian sampling process has a probability of being k-unstable that is proportional to $e^{\lambda - k}$"
- l.317 incomplete sentence: "... identifies which feature The key here ..."
- l.323 "an feature" -> "a feature"
- l.358 "We also explored" -> "We also experimentally explored"
limitations_and_societal_impact: I think the assumptions needed to show the result are perhaps a limitation worth mentioning (or mentioning again outside of the introduction).

1. Lasso estimator: the results would be stronger if the adversary was competing against an arbitrary learner (though the Lasso analysis is interesting in its own right). 

2. There is no limitation on the knowledge and computational power of the adversary as indicated in the proof of Prop 3.5: "After getting the dataset [X | Y] the adversary inspects the dataset to find out which coordinate is unstable and find a poisoning dataset that would add that unstable coordinate to the support set of the model." (l. 768-770) -> the instability is characterized by the existence of a poisoned dataset that causes the supports of the feature vectors gotten by Lasso on clean and poisoned data to differ. I believe this assumes that the adversary has a way of finding such a dataset -- it would perhaps be worth highlighting this again, even if it was touched on in the introduction (l.118-120).

3. Distributional knowledge: the fact that the adversary knows the distribution of the data seems like quite a strong assumption -- though the separation result remains interesting (the authors adequately address this limitation on lines 97-99; it would be perhaps worth adding whether this is a common assumption for poisoning attacks in the literature).
review_title: null

Meta-review: The paper got a score of 3786, while all 4 reviewers have concerns about the narrow field of the paper, i.e., only focused on LASSO and did not provide analysis on the widely used neural networks. In the authors' rebuttal, the authors evaded the question and said their result is just the first step. After discussing with SAC, the thoughts that having access to the actual data is more important than we might have otherwise thought is indeed interesting, i.e., the attack can be still weaker than data-aware one even we can estimate the distribution from publicly available data. Although the newly designed problem has some strong assumptions and may not be so practical, it provides some new insights on the poisoning attack research. Thus, the paper can be accepted if having slots. 
Decision: Accept (Poster)