Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: This paper proposes Aligned Dual Gradient Pruning (ADGP) as a defense against gradient inversion attacks.

A gradient inversion attack takes the gradient $\nabla W (x)$ (and the model $W$) and attempts to reconstruct the input data $x$.

Standard gradient pruning takes the gradient $\nabla W (x)$ and zeroes out the smallest coordinates. Intuitively, this makes it harder for the attacker as they are not given as much information.

Dual Gradient Pruning (DGP) zeroes out not only the smallest coordinates but also the largest coordinates, leaving only the "median" coordinates of the gradient.

ADGP modifies DGP by ensuring that all the participants zero out a similar set of coordinates, rather that independently choosing which coordinates to zero out.

The paper provides both experimental and theoretical analysis of ADGP. It give theoretical results that bound the error of a potential attacker. And it also gives experimental results where attacks are run against ADGP. This includes a comparison to other defenses and a utility analysis.
strengths_and_weaknesses: Strengths:
 - This paper studies an important problem.
 - It proposes a simple and novel approach to protecting against gradient inversion.
 - Both theoretical guarantees and empirical evaluation are included.


Weaknesses:
 - The theoretical results are somewhat difficult to interpret. E.g. the parameters $\gamma_1$ and $\gamma_2$ from Assumption 1 appear in Theorem 1, but it is not clear what these parameters are and, hence, how to interpret the guarantee.
 - The experimental results do not consider varying the parameters $k_1$ and $k_2$, namely the number of large and small coordinates to zero out. Similarly the other defenses being compared against also have parameters that could be varied.
 - Some details about the results are unclear (see below).
questions: I have a question about the theoretical results (Proposition 1) and the experimental results (Figures 1 & 2).

What is the optimization problem that the attacker is solving?

Abusing notation slightly, I can see two possible ways to do this: First, $$\arg\min_{x'} \\|\nabla W(x') - \mathsf{ADGP}(\nabla W(x))\\|$$ and, second, $$\arg\min_{x'} \\| \mathsf{ADGP}(\nabla W(x')) - \mathsf{ADGP}(\nabla W(x))\\|.$$
Which of these two is being considered in the paper? or is it something else?

Intuitively, my question is how does the attacker account for the ADGP defense?

I also have a minor question about Definition 1. There is a nested probability and expectation. What is the source of randomness for each of these?

---

The discussion with the authors clarified the question about what optimization the attacker is performing, namely $$\arg\min_{x'} \\|\nabla W(x') - \mathsf{ADGP}(\nabla W(x))\\|.$$ 
Unfortunately, this is the wrong way to formulate the problem. Intuitively, this assumes the attacker is not aware of the ADGP defence being used and applies a naive strategy. More precisely, the problem is that this objective is not minimized by $x'=x$ -- i.e., this objective does not lead to successful reconstruction.

This issue essentially invalidates the experimental and theoretical results. They assume a naive attacker and tell us nothing about what an attack tailored to this defence would do.

In the discussion I presented a simple counterexample to Theorem 1 in the paper. That is, the loss $\ell(w,x) = (x-\sum_i w_i)^2$, where $x$ is a scalar and $w$ is a vector. Given any single coordinate of the gradient and the value of $w$, it is possible to reconstruct $x$. ADGP does not protect against this attack.

The experimental results attempt "state-of-the-art" attacks. The problem is that an attack is tailored to a specific system. A state-of-the-art attack for one system may not be state of the art for another system.

Unfortunately, given this major flaw, I think the paper cannot be accepted.
limitations: Limitations are discussed
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper considers an important and timely problem in Federated Learning, investigating defense mechanism against model inversion attack in terms of three key metrics: privacy, utility, and communication efficiency. To provide better trade-off among the three key metrics, this paper firstly proposes a simple sparsification technique, named dual gradient pruning (DGP), which removes top-k1 largest values and bottom-k2 smallest values in local model parameters. In the second component, named gradient location bounding, communication cost is further reduced by ensuring that the sparsified region of different users are the same.
This paper theoretically shows that proposed scheme guarantees better privacy against model inversion attack. In addition, convergence analysis of the proposed method is provided with IID dataset distribution (i.e., local computation of each user is unbiased to the full gradient) and assumption on DGP. 

strengths_and_weaknesses: Overall, this paper is well structured and written, and hence easy to follow. Intuition behind the motivation of DGP/ADGP is well described in the section 4. While the proposed pruning technique is very simple, it can incur further research investigating privacy and utility trade-off in sparsification/pruning schemes in FL. Especially, combining sparsification and other defense mechanism (DP, secure aggregation, etc) would be very interesting future direction. It also includes extensive experiments with various attack models and defense mechanisms to demonstrate the stronger privacy guarantee and comparable utility of the proposed scheme. 

I have the following concern/comment:

1. In theoretical analysis, it seems that this paper relies on strong and unrealistic assumptions. This paper considers IID data distribution (i.e., in assumption 3, local stochastic computation is unbiased to the full gradient), which is not the case in FL. In addition, as the assumption 1 is very important for the analysis of convergence, more justification/explanation is needed. For instance, while k1 is an important parameter which determines the utility (and convergence performance), relationship between \gamma_2 and k_1 is not presented. 

2. In section 4, the role of e_i^t is not described. We can know that it is accumulated error of user i at round t in section 5 (after reading the lemma 1, but it is helpful to understand the proposed scheme if explanation will be included in section 4. 

questions: 1.	How can we represent gamma_1 and gamma_2 with respect to k_1, k_2, and k?
2.	In experiments, what is N (number of users), and how the dataset (CIFAR10/100) is distributed over N users?

limitations: As this paper considers the privacy in FL, it has no negative societal impact.
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 proposes a defense against Gradient Inversion Attacks (where input images can be reconstructed by an attacker from the public gradients).
- The crux of the proposed approach is (a) pruning gradients: where top-$k_1$ and bottom-$k_2$ parameters are pruned and (b) gradient-location bounding: such that users across FL prune similarly which results in sparsified models even at download-time.
- The paper is also accompanied with theoretical insights validating the choices e.g., perturbed vs. non-perturbed gradients are proportional to reconstruction errors.
- The defense approach is evaluated against three attacks (Rob, IVG, R-GAP) and two datasets (CIFAR10, CIFAR100). Evaluation indicates a performance improvement over existing defense against all attacks, while retaining the utility (efficiency, accuracy).
strengths_and_weaknesses: ### Strengths
1. Insight: The core insight is intuitive. Existing top-k approaches *retains* the top-k parameters and the authors show that this results in keeping the sparsified gradient close to the original and thereby increasing the attack effectiveness (Proposition 1). In contrast, the approach *prunes* the top-k gradients and thereby lowering the reconstruction performance.
2. Evaluation: The authors benchmark the approach against multiple classes of GIA attacks (analytical, optimization-based, ...).
3. Results: The results are significant and promising. The approach while almost perfectly retaining the target model accuracy (93.17 vs. 93.44) thwarts all considered classes of attacks.

### Concerns 
1. Gradients attacked from which iteration?: The evaluation methodology is slightly unclear. Specifically, it is unclear the gradients from which training iteration is used to demonstrate system-under-attack performance. Are the authors aware whether this has an impact to attack performance? I reckon the gradients at the early training iterations are more
2. Choice of attacks: While I appreciate the authors consider different classes of attacks, some recent popular attacks seem to have been left-out e.g., GradInversion [26]. Specifically, the class of optimization-based attacks which additionally regularize fidelity. 
3. Some evalution details unclear: While the paper indicates evaluation on 2x CIFAR10 models and CIFAR100, it is often not clear for which model/dataset the results are. For instance, the setting is unclear in Fig.1 and Table 2 (which I think is CIFAR10?), but Fig. 2a displays attacks on CIFAR100.

questions: Please see the questions under concerns.
limitations: Yes, the authors have adequately discussed the limitations in the main paper.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper proposes a new gradient pruning strategy called "Aligned Dual Gradient Pruning" for federated learning (FL). It differs from the standard pruning approach of top-k sparsification in two ways - (i) instead of retaining the top-k gradients, it removes both top-k1 and bottom-k2 gradients, thereby increasing the distance between the original gradients and the exchanged gradients, and (ii) one of the clients is allowed to broadcast the locations of its top-2k gradients, so that all the other clients can choose from this list of locations while picking the gradients to transmit. 
strengths_and_weaknesses: Strengths:

1) A variant of the top-k gradient pruning strategy has been proposed to enhance robustness against gradient inversion attacks (GIAs). 
2) Both theoretical results and experiments have been presented to demonstrate that the proposed method works.

Weaknesses:

1) It is fairly obvious that if the top-k1 gradients are suppressed, it will lead to less information leakage compared to top-k sparsification. However, it is hard to believe that it will have no effect both on the convergence speed and final accuracy. Though the paper provides a theoretical result (Theorem 2) and experimental data (Table 2 and Figure 4), a concrete intuitive explanation of this unexpected behavior is required. Is this solely due to the error accumulation step? How will the proposed method behave if error accumulation is removed?

2)  There is no mention about non-iid data in the whole paper. One would expect that the proposed alignment strategy will completely breakdown in the case of non-iid data, because there will be very few intersections between the top gradients of different clients. A careful analysis of this issue is clearly necessary.

3) The most critical weakness of the paper is the lack of any analysis about the privacy leakage introduced by the alignment step. Since one of the clients transmits the binary matrix $\mathcal{I}$, it is trivial for the server to know the locations of the top 2k gradients of this client. Even if the client does not transmit the top-k1 gradient values, the server knows that locations with value 1 in $\mathcal{I}$ must have values greater than or comparable to that of the gradients that are actually transmitted by the client. Wouldn't this leak more information about the client's gradients compared to even the top-k sparsification strategy? Does any of the attack techniques considered in this paper exploit this knowledge?

4) There is no ablation study to evaluate the impact of the various components, especially alignment step and error accumulation step.
questions: 1) What is the contribution of the error accumulation step? How will the proposed method behave if error accumulation is removed?

2) If the server keeps an account of the gradients transmitted by the client in each round as well as the locations of the top-2k gradients, can the server recover almost the full gradient of the clients over a few rounds of communication?

3) How will the proposed alignment scheme work in the presence of non-iid data?

4) What is the privacy impact of the alignment step? Will it leak more information than top-k sparsification since the server knows the locations of the top-2k gradients? Can more sophisticated attacks be designed leveraging this information?

5) What is the impact of the hyperparameters (k1, k2, and k) on convergence, accuracy, and privacy? 

 
limitations: The paper discusses one limitation related to the assumption that all the clients need to be honest for the proposed scheme to work. But it overestimates the privacy benefits of the proposed approach.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper continues the research line of defending against data leakage in federated learning (FL). In particular, the paper argues against the conventional view that the top-k defenses do not work well, and proposed a simple modification, which is to also remove bottom gradients and then perform a calibration based on the accumulated error from the previous rounds to reduce communication cost. The paper compares the performance with five existing defenses on three existing attacks, and show that their method can achieve a better utility-privacy-communication tradeoff.
strengths_and_weaknesses: Strengths
- Important topic: the data leakage problem in FL is a practical concern
- The method is simple and easy to implement

Weaknesses
- The theoretical part has several places that are unclear and questionable to me (see Questions section)
- The evaluation section show some results that do not seem comparable (see Question section)
questions: 1. The authors point out why top-k does not perform well: (1) top-k gradients are close to the real gradients and (2) large gradients leaks information of $y$. Both reasons only explain why top-k might be problematic, but how does removing bottom gradients address both problems? I do not find any insights that explain it, the only sentence I find that gives some justifications is "Moreover, it is also necessary to delete small gradient parameters to achieve a high sparsification ratio." (Section 4.2), which only says deleting small gradients can make sparsification ratio higher. But deleting any gradients can further sparsify, why small gradients? Please clarify.

2. Definition 1: Change $\mathcal{D}_{(\nabla W, \nabla W^*)}$ to $\mathcal{D}(\nabla W, \nabla W^*)$. Usually $D(.,.)$ represents the distance and there is no need of subscripting.

3. Proposition 1
- From the supplementary material, $\phi(x, W)$ is just $\nabla W$, you should define it explicitly in the main text. In addition, why write $\nabla W$ twice in the right-hand side of the inequality but in different forms (in both numerator and denominator)?
- Define $g = \phi(x', W)$ (taken from the supplementary material) explicitly. Propositions should be self-contained.
- The conclusion that "reconstruction error is proportional to the gradient distance $||\nabla W - g||_2$" seems questionable to me because the denominator is not a constant. In fact, if I understand it correctly, the denominator is the 2nd derivative of $W$ w.r.t $x$, i.e the Hessian norm, is it correct? If so, I do not see why the reconstruction error can be proportional to the numerator. Please let me know if I misunderstand it.

4. Algorithm 1: Where is the part that removes the bottom gradients $\mathcal{B}_{k_2}(\nabla W)$? It seems it only operates on the top gradients.

5. Assumption 1: $\gamma_1$ and $\gamma_2$ are constants determined by $k_1$, $k_2$, and $k$. What are their explicit definitions? Please write them out because they are used in main theorems and lemmas and should not be undefined.

6. Table 2
- The comparison of DP with other defenses are not apple-to-apple because the DP accuracy is much lower. I notice the reason you choose that DP budget was because it has been shown the best in the prior work. But in this particular evaluation, if you do not tune the DP budget to find a comparable accuracy, the privacy protection performance comparison is not fair.
- In R-GAP, the SSIM row, the best defense ("Ours") is not highlighted.

7. In general, the author should not make claims against the utility-privacy-communication tradeoff like "none of the existing defense methods could take care of all privacy, utility, and efficiency difficulties in FL" (taken from the introduction). Because there is a fundamental tradeoff and this paper (and maybe all papers) cannot remove the tradeoff. They can only make a better tradeoff but cannot make it go away. Therefore, I think it would be a more objective tone not to emphasize the tradeoff exists in the prior work (since it exists in any method) but rather the tradeoff is not good enough.
limitations: I do not have comments on the limitations.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper introduces two techniques, Dual Gradient Pruning (DGP) and Aligned Dual Gradient Pruning (AGDP) to protect against gradient inversion attacks. They describe DGP and present ADGP as an improved version of DGP that has the same security considerations but lower communication costs. They show that optimization attacks have a provable amount of degeneration under DGP and ADGP. Then they empirically evaluate their technique against a set of gradient inversion attacks and compare against other defenses like DP-SGD, Soteria and Precode. The authors show that their ADGP technique succeeds against all the attacks they try while still maintaining model quality and reducing communication costs.
strengths_and_weaknesses: Strengths
- The authors present a very simple idea and run extensive experiments to show that their technique is superior to existing baselines
- DGP by itself seems like a new and somewhat unintuitive technique and the results from DGP would be a fairly strong contribution by itself.
- Empirical evaluation and comparison with other techniques is very thorough. The authors compare against most of the well-known baselines and try multiple attacks. The details of the empirical evaluation are also clearly specified in the main text.

Weaknesses
- Assumption 3 seems somewhat unrealistic. Assuming that each client in each round has data that provides an unbiased gradient means that the data has to be IID distributed across clients. 
- ADGP is presented as saving communication overhead but this overhead is only saved if the same set of clients are used for every round of FL training. If the clients selected for round N are different from those selected for round N+1 then ADGP does not save any communication overhead. In production FL settings, clients are often selected from a large population, so the odds of the same client appearing in two back-to-back rounds are low.
- The authors only evaluate on vision models, but there are known gradient inversion attacks in NLP, speech etc. It would be interested to see if DGP works in those settings.
questions: Does the analysis still hold if assumption 3 does not hold?
Did you try your technique on domains other than vision?


limitations: Negative impacts are adequately addressed.
review_title: null

Meta-review: metareview: This paper proposes a method for defending against gradient inversion attacks.
A gradient inversion attack attempts to reconstruct the training data from the model and its gradient.
Gradient inversion attacks have been performed in practice, which demonstrates that sharing gradients rather than raw data provides limited privacy protection.

The proposed method,"Aligned Dual Gradient Pruning (ADGP)," perturbs the gradients by zeroing out a large subset of the coordinates including both small and large values.

The key claim is that this prevents reconstruction of the training data.
The paper provides both theoretical and experimental results to support this claim.

However, these results rely on implicit assumptions about the form of the gradient inversion attack. Specifically, they assume a vanilla gradient inversion attack that does not compensate for the ADGP defense. In particular, ADGP creates sparse gradients and it is assumed that the attacker attempts to reconstruct an input whose unperturbed gradient is sparse, even if the true unperturbed gradient is not sparse.

This assumption is a form of "security through obscurity." We should assume that the attacker is aware of the defense and tailors the reconstruction to the defense. Thus theoretical/empirical evaluation should consider attacks that are designed specifically for ADGP.

Overall, the key claim of the paper is not adequately supported (and, in my opinion, it seems likely that the proposed defense is not effective). Thus this paper should not be published.
confidence: Less certain
Decision: Reject