SPEAR: Exact Gradient Inversion of Batches in Federated Learning

We thank the reviewer for their very positive review. We are particularly happy to read that the reviewer assesses our contribution to be of great value and finds the comparison to related work convincing. We will include all proposed writing suggestions. We now address all questions of the reviewer.

Q1: Can SPEAR handle activation functions different from ReLU?

We direct the reviewer to our previous answer to question Q2 in the general response. In this work, we focus on the most common ReLU activation as it is the most relevant one in practice. Further, we believe that transferring our insights to other activations is a valuable item for future work.

Q2: For experiments in 6.2, are the image labels known for the reconstruction ahead of time?

No, we do not require the knowledge of labels at all. We do want to emphasize that the only prior we utilize is the ReLU-induced sparsity.

Q3: Why can SPEAR fail when the batch size is larger than 25? Is this handled by the probability of failure analysis?

We refer the review to our answer to Q1 in the main response. As outlined there, the failure probability for reasonable network widths is not a significant bottleneck for the batch sizes we experimented with. Instead, the bottleneck is the number of submatrices $L_A$ one needs to sample to recover all the correct directions $\overline{q}$, which is analyzed in Lemma 5.2. In practice, we limit this number to fit in a reasonable time limit and we report a failure otherwise. We emphasize that SPEAR, in theory, is capable of recovering inputs for batch sizes $> 25$ provided enough time. As outlined in the general response to Q1, one can use approximate reconstruction methods to guide the search for those submatrices, lifting the restriction, and allowing exact reconstructions for batch sizes as large as 100. Finally, we provide experiments in Appendix E5, showing that the predicted failure probabilities agree well with empirical results for small to moderate layer widths.

We are happy to discuss any remaining or follow-up questions the reviewer might have.

We thank the reviewer for their positive review. We are happy to read that they find our contribution insightful and inspiring future work and credit our significantly better performance and theoretical analysis. Further, we are glad the reviewer deems the paper nicely structured.

Q1: Can the exponential sample complexity of SPEAR be improved? Is the probability of failure a bottleneck in practice?

Yes, the exponential sample complexity can be addressed, as we discuss in the general response (Q1). Specifically, there we show that SPEAR can leverage optimization-based methods to circumvent the exponential sampling-based information retrieval to scale to much larger batch sizes while still providing (almost) perfect reconstruction, and we clarify that the failure probability is not currently a bottleneck (see also Figure 3 in the main paper).

Q2: Is the algorithm effective for high-resolution datasets like ImageNet?

As highlighted in the abstract, SPEAR reconstructs batches of sizes up to 25 on ImageNet exactly. We provide more corresponding results in Section 6.2 (Main Results). Specifically, we run experiments on the commonly used resolution of 224x224 for ImageNet and also on a 720x720 high-resolution setting to showcase our scalability even further. We note that this is, as shown in Table 3, at the very moderate cost of a runtime increase from 2.1 minutes to 2.6 minutes per batch. This is significantly faster than prior work as shown in Table 1, where we compare various works on ImageNet using a resolution of 256x256. Could the reviewer clarify the question in case we misunderstood it?

Q3: Does the effectiveness of the algorithm rely on the assumption that the first layer of the network is a linear layer?

No. As discussed in Q3 of the main response, SPEAR can be efficiently applied to any linear layer that precedes or follows ReLU activations to obtain that layer’s inputs. Even when the attacked layer is in the middle of the network the intermediate inputs recovered via SPEAR pose an increased risk to the privacy of the client data. We demonstrate the practicality of using SPEAR on linear layers in the middle of the network by attacking VGG16, as shown in Table 1 in the rebuttal PDF. See Q3 of the main response for further details. Further, we emphasize that our method is a significant theoretical advancement over prior work, providing novel insights into the gradient leakage problem as acknowledged by the reviewers. We focus on ReLU with linear layers to open the field for further research. There is already very promising future research building on the insights gained in this work. See our answer to Q6. Finally, for tabular datasets, networks starting with a linear layer are common. In this setting SPEAR outperforms all prior work by a wide margin in terms of input reconstruction quality and speed, particularly when no further priors are given.

Q4: When the batch size increases, is there a trade-off scheme that sacrifices the fidelity of recovered images but reduces the running time?

Yes, the threshold we use to test if an entry in $L \overline q_i$ is 0 can be tuned. As we use this test to filter out wrong proposal directions (see Section 4.1), high thresholds can permit directions computed in a numerically unstable way (e.g. due to applying Theorem 3.4 on matrices $L_A$ that are not so well-conditioned), leading to lower reconstruction quality but faster runtime. While tuning this threshold can yield a noticeable speedup, it does not address the exponential nature of our algorithm However, if one would like to resolve the exponential runtime of SPEAR, we propose a combination with an optimization-based method to get priors on the signs of $Z$. Please see our reply to question Q1 in the main response, where we discuss in detail how this allows SPEAR to scale to significantly larger batch sizes while retaining exact reconstruction.

Q5: Can the algorithm deal with normalization layers?

As Batch-Norm layers compute batch statistics at training time and then use these statistics to normalize the activations, they entangle the gradients of all batch elements. This makes the analysis of the gradient structure significantly more complex and prevents us from directly applying SPEAR as now the output of the BN rather than the linear layer has sparse gradients. On the other hand, this normalization and rescaling allows us to compute a very precise estimate of the expected sparsity for the ReLU inputs $Z$ and thus improve our filtering described in Section 4. While we have promising initial results addressing this issue, SPEAR requires significant non-trivial adaptations for BN-layers, which we believe is an interesting item for future work.

Q6: Can the algorithm be adapted to convolutional networks and (vision) transformers?

Yes, there is recently published work on Transformers relying on insights from this work, that also significantly outperforms all prior work. We contacted the chair to share this work with you. For applications to convolutional networks, please see our reply to Q3 in the main response.

We thank the reviewer for the very positive review and are excited that the reviewer finds that SPEAR marks a significant advancement for gradient inversion. We are also happy to read that the reviewer attests that our method builds on a strong theoretical basis and credits our soundness, presentation and contribution. We answer all of the reviewer's questions in the general response:

Q1: SPEAR is effective for a moderate batch size of b < 25. What is preventing SPEAR from scaling beyond this?

Please see our detailed reply in the main response (Q1).

Q2: Can SPEAR handle activations beyond ReLU?

Please see our detailed reply in the main response (Q2).

Q3: Can SPEAR handle layers other than fully connected layers?

Please see our detailed reply in the main response (Q3).

We are happy to discuss any remaining questions or follow-up questions the reviewer might have.

We thank the reviewer for their positive review and are glad to read they found our contribution really interesting, the proofs clean and precise and the reconstruction quality really good.

Q1: Can SPEAR scale to batch sizes greater than 64?
Yes, we address this in the general response (Q1). Specifically, we show that SPEAR can leverage optimization-based methods to scale to significantly larger batch sizes while still providing (almost) perfect reconstruction.

Q2: Can SPEAR handle a linear layer that is preceded by a conv layer?
Yes. We added an experiment showing perfect reconstruction results for VGG16 and $b=20$ in Table 1 in the rebuttal PDF. Please refer to Q3 in the general response for more information about this experiment.

Q3: Can you provide experiments, where SPEAR reconstructs inputs to linear layers that are not the first one?
Yes. We consider a 6-layer network with 400 neurons in each layer and a batch size of 20 and report the mean absolute error (MAE) to the original activations in Table 2 in the rebuttal PDF. Our experiments indicate that we can recover almost all inputs to all layers (almost) perfectly. Please refer to Q3 in the main rebuttal for more details about this experiment.

Q4: Are the provided visualizations representative? Can the authors provide more visualizations of the SPEAR’s results?

We want to clarify that the visualizations provided in Figure 1 of the main paper are a subsample of the visualizations provided in Figure 9 in Appendix G, where we visualize the corresponding full batch. The batch in Figure 9 is representative as it was randomly chosen and has a PSNR similar to the overall PSNR mean. To reaffirm this point, we provide further batch visualizations in Figures 1-3 in the rebuttal PDF. These visualizations are in the same setting as Figure 1 of the main paper, but their corresponding batches are chosen to represent the $10^{\text{th}}$,$50^{\text{th}}$, and $90^{\text{th}}$ percentiles of the obtained PSNRs in this experiment. We observe that only 1 sample is not perfectly reconstructed for the $10^{\text{th}}$ percentile batch (which we show in its corresponding figure) and that the $50^{\text{th}}$ and $90^{\text{th}}$ percentile batches contain only perfect reconstructions.

Further, we note that Figure 10 in Appendix G visualizes the batch on which SPEAR performed the worst on TinyImageNet. Manual inspection showed that its poor performance is caused by SPEAR failing to recover one of the directions $\overline{q}_i$. We will clarify these points and provide further visualizations in the next version of the paper.

Q5: What is SPEAR’s performance under rigorous DPSGD guarantees?
We want to clarify that the results in Appendix E.6 were obtained by adding Gaussian noise to the gradient, as a viability test of SPEAR’s robustness against noisy gradients. Specifically, we did not do the gradient clipping necessary for DPSGD. We will clarify this in the paper and also provide new experiments, showing SPEAR’s results in the DPSGD setting alongside the corresponding $(\epsilon,\delta)$ guarantee.

I did run the code provided by the author again, and the reconstruction results are fantastic. I am willing to raise my score since the authors addressed all the questions I asked. I believe this method is ground-breaking for gradient inversion attacks in general. Other recent works tend to use diffusion/GAN to enhance their reconstruction results, but this work perfectly reconstructs the linear layer's result and demonstrates the possible vulnerability of LL in many NN architectures.

I just had a few detailed questions regarding implementation:

1. For VGG-16, are you running at linear shape = 1 1 4096 layer?
2. for implementation part, could you put Q_opt sperate only for extra evaluation function? I was confused and first thought you directly used GT in the reconstruction process.