Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper studies data and model poisoning attacks in federated learning (FL). It argues that there is an equivalence between data poisoning and model poisoning attacks, by restricting attention to linear and logistic regression. The main technique is to leverage ideas from PAC-learning. Another key contribution is to propose a gradient poisoning attack.
main_review: Model poisoning are generally perceived as stronger attacks (in terms of poisoning impact) than data poisoning attacks, simply because data poisoning only indirectly manipulates a client’s model update. Therefore, showing an equivalence as the paper argues would be very interesting. However, in my view, the paper is written in somewhat confusing manner, and lacks in details. Therefore, it is difficult to understand and assess the claims. (More detailed comments are given below.) Moreover, the paper does not compare the proposed Counter-Gradient attack with existing attacks. There are a large number of existing attacks and defenses, and it would be important to place the proposed attack in the larger context by comparing and contrasting with prior attacks and defenses.

Detailed Comments:

1. Definition 1 relies on ‘true models’ \theta^{perp}. It will be good to give more details about what do the authors mean by true models. Propositions 1 and 2 on computing poisoned gradients also use true models. It is not clear how users will know about these true models? It will be important to elaborate this further. 

2. Is the difference between using sum vs. expectation in the loss not related to empirical vs. population risk? Also, computing the sum  of losses over the entire user dataset is essentially gradient descent, which is known to be computationally burdensome. It will be helpful to comment on these points.

3. In Definition 2, a loss function is defined to be PAC-learnable. This is a bit confusing. PAC-learning is usually defined for a class of functions. It would be good to explicitly define the function class. 

4. In Theorem 2, how is \tilde{Q} defined and how is the Supp() defined?

5. Theorem 1 restricts the queries to be i.i.d. sub-Gaussian. This seems to be quite restrictive. It will be good to comment on this. 

6. Theorem 5 requires that a user’s dataset contains at least \mathcal{I} inputs drawn from a certain model. This is quite confusing. What does it mean to draw inputs from a model?

7. The paper says that [Shejwalkar et al. 2021] argued that model poisoning attacks are not realistic, and claims in the conclusion that their findings reverses this argument. It is not clear why an equivalence result would reverse the claim in [Shejwalkar et al. 2021]. This is because, as per my understanding, [Shejwalkar et al. 2021] also argue that data poisoning attacks are not very impactful (key lesson (2) on page 2). It would be important to give more details here. 
summary_of_the_review: It would be interesting to show an equivalence between model and data poisoning attacks in FL. However, the paper is written in somewhat confusing manner and lacks in details, which makes it difficult to understand and assess the claims.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper reveals the inherent equivalence between gradient and data poisoning attacks in personalized federated learning settings. The authors showed that any gradient attack can be transformed into data poisoning in a personalized federated learning system that provides PAC guarantees. This new insight challenges the view that (Byzantine) gradient attacks are unrealistic. The authors built this equivalence by constructing a model attack for personalized federated learning models. The authors showed the effectiveness of this attack both theoretically and empirically. 
main_review: Strengths:
+ Reveals a new insight on the equivalence between Byzantine gradient and data poisoning attacks, which is an important and timely topic.
+ A novel PAC framework for analyzing personalized federated learning performance.

Weaknesses:
- Gradient attack model is limited.
- Experiments are limited to simple datasets.
summary_of_the_review: This paper reveals an equivalence between Byzantine gradient and data poisoning attacks in the context of personalized federated learning, which is an important and timely topic. This insight suggests that the claims in the existing literature that Byzantine gradient attacks are unrealistic is misleading. To my knowledge, this result is new and its contributions to the field are significant. However, this paper also has several issues, which are listed as follows:

1. The attack model considered in this paper is somewhat simplistic in that the authors only considered the single-strategic-user case. Although it is understandable that this renders the problem more tractable for theoretical analysis, the results may not be very useful because Byzantine gradient attacks are not necessarily from a single malicious user. In fact, most works on Byzantine gradient attacks allow multiple Byzantine workers. It's unclear whether the results in this paper could be extended to multi-attacker scenarios.

2. The authors proposed a PAC framework as a foundation to evaluate the performance of various Byzantine and data poisoning attacks. To my knowledge, this is also a new and interesting contribution. The authors demonstrated the relevance of this PAC framework by showing that linear regression and classifications are PAC learnable under this framework. But I wonder whether this PAC framework continues to be meaningful for more complex learning models than linear models. Having further discussions on this aspect would be very interesting.

3. Most of the experiments in this paper are conducted on MNIST and Fashion-MNIST datasets, which are relatively simple. It would be more interesting to demonstrate the claimed equivalence between attacks on more sophisticated datasets. Also related to the previous comment, most of the experiments are based on linear models (a simple two-layer neural network is also used). I think this paper could benefit from more experiments with more sophisticated learning models.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper shows an equivalence between data poisoning attacks and gradient attacks that attack gradient descent on personalized federated learning setting for certain convex loss functions. 
main_review: The goal of this paper to compare two threat models in federated learning 1) data poisoning attacks that inject a number of poisoning examples to the training set 2) gradient attacks that change the update gradients sent during the federated learning operation by malicious agents. They specifically study the personalized federated learning setting where N machines collaborate to train N personalized models and a single global model. In this setting, the loss function is defined in a way that the global model and personalized models have dependencies to each other through an additive regularization that controls how far the personalized models can be from the global model.

The paper first defines two notions that they call PAC^* Learning and gradient PAC* learning for the personalized federated learning. The notion of PAC* learning is about finding a set of personalized models that are close to the set of true models with respect according to some metric. Note that this is different from PAC learning because they care about distance, rather than accuracy. They also define gradient-PAC*, which requires the gradients of the personalized models with respect to any global model \rho to be close to that of true models.

Then, they introduce a hypothetical threat model called a model attack, where they fix one of the personalized models to a specially crafted adversarial model. Then they show that, if the optimization of loss function has PAC* learning abilities, then the adversary can simulate the effect of the model attack using data poisoning attack, by poisoning all of the data for the machine, if the number of data-points provided by that machine is larger than some threshold. This result is expected, because as the number of data-points grow, the dependence between the personalized model and the global model decrease (because of the diminishing effect of the regularization). Then, by increasing the number of data points, because of PAC* learning, the adversary can change the personalized model to a adversarially crafted model, by using queries that are labeled accordingly. At the same time, the global model and other personalized models would not change much because of the diminish dependency of the global and personalized models.  

Now the remaining step is to show that the gradient attack can be simulated by a model attack. In order to show this, they need some strong assumptions. For instance, they need the loss function to be strongly convex. They need the poisonous gradients to be valid gradients according to the global model. and also they require the poisonous gradients to converge. This step is technically interesting and novel, in my opinion. 

Finally, they design a data poisoning attacks that are inspired by the steps mentioned above. They empirically show that this attack is effective in linear regression.


Limitations:

- The final equivalence result of the paper only applies to simple settings with strongly convex loss functions and seems to only work for GD optimization.

- The presentation of the work is not in publication stage. It is really hard to understand the main claims of the paper.

- Some discussions about the implication of the results are missing


Comments/Questions to authors:

1- I have read through the paper multiple times, but I still do not understand the exact threat model of gradient attack. I think you need to define this explicitly.

2- The notions of PAC* learning are not defined properly. There are terms such as "true model"  and "honest dataset" that are not defined. These terms are not standard and must be defined. Also, there is a probability \delta, what is this probability over? 

3- Section 3 seems to be completely out of context. Why do you need to justify the choice of loss function before describing the main results? I was really confused by this section. After reading the paper, I realize that you need to define the loss this way in order for Theorem 5 to hold? If this is correct, you need to explicitly mention it. I also find Table 1 confusing. 

4- Defining the loss function as a summation of the loss is fine, but your notion of PAC* learning talks about large number of data points. Wouldn't large number of data points make the dependence of global and personalized models weaker as more data is provided? How is it justified to keep the regularization the same as more data is provided?

5- Again, section 4 seems to be out of place. It is a bit odd to see the main results of the paper in section 5. I would recommend to  change the order of sections 4 and 5.

6- The equivalence between the model attacks and data poisoning attack depend on the number of data points. I think the paper needs discussion on this connection. Could the power of model attacks be significantly higher than data poisoning attacks when the number of data points provided by each party is a fixed and perhaps small number?

7- Theorem 6 seems like the main theorem in the paper to me. But I cannot verify the proof. Specifically, I cannot verify equation (120) in page 33. Can you explain why this is the case? Aren't \rho and \theta_n getting optimized together. In your formulation it seems like \theta_n is optimized until convergence for each intermediate \rho. 
summary_of_the_review: I find the topic of this paper extremely interesting. Understanding the relation between gradient attacks and data poisoning attacks are very important. This paper takes an initial step in understanding the relation between these two attacks for simple models such as linear regression. However, as stated in my comments, I have serious concerns about the presentation of this work. The main ideas presented are not easy to comprehend. The exact threat models are not also clearly specified. I also have some concerns about the proofs (In particular about equation 120, page 33). I will be happy to increase my score if authors can provide sufficient response to my concerns.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper formalizes the concept of PAC*-learnability for a generalized personalized federated learning model and provides a sufficient condition. Under this model, converging gradient attack is equivalent to data poisoning. The paper also proposes the counter-gradient attack that is effective and data-efficient.
main_review: The considered problem is of great contemporary importance in the deployment of large-scale machine learning systems. 1. The formalization of the PAC learnability is intuitive and concrete examples linear regression, logistic regression, are analyzed to illustrate this definition. 2. The equivalence between data poisoning, model attacks, and gradient attacks are carefully analyzed. 3. The proposed CGA attack has theoretical guarantee and demonstrates good empirical performance.

In general, I think the assumptions used in this paper are strong. 1. The sufficient condition proposed for PAC* learnability is not intuitive to me, is more like a sufficient condition for the two concrete examples analyzed, and lack intuitions for a wider class of functions. Like, does this condition or the PAC* learnability holds for any non-convex loss used in practice? 2. It might also help to have more detailed explanations for the considered data poisoning, model attacks and gradient attacks, like giving concrete examples to illustrate. The assumptions for theorem 6 to hold also seem strong to me, it is not clear to me how to interpret the assumed property of R, especially R(\rho, \theta) = R_0(\rho - \theta). It might be clearer to draw a diagram to show under which conditions the claimed equivalences hold, since the claim in the paper title and abstract is fairly strong. 3. I also would suggest giving proof outlines for main theorems for the paper. 4. Another question is how should we relate the proposed CGA with the previous sections, is there any motivations therein?

summary_of_the_review: I would recommend that the paper is marginally below the acceptance threshold. Mainly because I don’t quite follow the intuitions of some assumptions. Refined analysis with weaker assumptions and clearer presentation would be appreciated.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper studies the relationship between Byzantine gradient attacks in distributed optimization and data poisoning. Some theoretical evidence is presented about the equivalence of these. A new gradient-based Byzantine attack is also presented.
main_review: Pros:

The paper studies an interesting problem, since both Byzantine attacks and data poisoning attacks have been extensive studied in the literature, but little is known about how these fields relate. The paper provides a substantial technical analysis, as well as a practical Byzantine attack.
 

##########################################################################

Cons: 

Unfortunately, several concern prevent me from recommending acceptance. 

- Firstly, I find the comparison to related work very insufficient. 

For the theoretical analysis a number of recent works, for example [1,2,3,4], have explored (robust) machine learning from multiple datasets from a PAC perspective. These essentially correspond to the notion of PAC* learnability presented here, with and without data poisoning. It is unexplained how these works compare to the current one. 

For the gradient attack that is designed, there is no comparison to prior attacks as well. It is also unclear what this attack has to do with the rest of the paper - can the authors explain?

- The paper is also slightly hard to follow, in particular the results of Theorem 4,5 and 6 are quite hard for me to interpret. Since there is no previously defined notions of success of for each of the attacks, it is hard to understand why the results imply any type of equivalence between the notions. Further discussion immediately after these results will therefore be helpful.

#########################################################################

References:

[1] A. Blum, N. Haghtalab, A. D. Procaccia, M. Qiao: Collaborative PAC Learning, NIPS 2017
[2] M. Qiao: Do outliers ruin collaboration?, ICML 2018
[3] N. Konstantinov, E. Frantar, D. Alistarh, C.H. Lampert: On the Sample Complexity of Adversarial Multi-Source PAC Learning, ICML 2020
[4] A. Jain and A. Orlitsky: A General Method for Robust Learning from Batches, NeurIPS 2020

 
summary_of_the_review: While the studied topic and the proposed notions and results are interesting, I believe that the paper will benefit from substantial further comparison to existing work and also from further discussion of the results from Theorems 4,5,6.
review_title: null

Meta-review: This paper presents an analysis showing the equivalence between gradient and data poisoning attacks in personalized federated learning settings. The paper contains an analysis of an attack that requires only a single corrupt learning agent, providing results in the setting of PAC learnable models.
The reviewers had several criticisms of the paper, some of which were addressed in the rebuttal.  The first is that the presentation of the paper was at times confusing, and the theoretical results were hard to interpret.  This has been addressed by several changes to the paper writing, including major changes to the layout.  The reviewers feel that other criticisms were not entirely addressed.  This includes the criticism that the experiments are in a fairly simplistic setting (GD on MNIST and Fashion MNIST), and that the theoretical results require strong assumptions and focus mostly on classical models that are learnable in convex frameworks.  While the reviewers agree there are interesting questions posed in this paper, the consensus seems to be that the experimental and theoretical results in this paper should be further revised, and that a future version of this paper will be a great candidate for publication.
Decision: Reject