Theoretically Understanding Data Reconstruction Leakage in Federated Learning

Comment#4: Problems with the presented evaluation

Comment#4A: Use two different scales for the bounds and the empirical results

Response: Thanks for the suggestion. Will do.

Comment#4B: the authors do not provide a correlation metric between their bound and the empirical evaluation results. Can the authors provide correlation metrics between bound and empirical results?

Response: Our theoretical results show that the one-snapshot empirical errors may not have a strong relation with the bounded errors. This is because one-snapshot empirical errors obtained by the existing attack can be significantly different under different initializations (as verified in Figure 1). However, Figure 9c shows that the error bound per attack has a strong correlation with its empirical errors in expectation. We tested that with the 10 initializations, the Pearson correlation coefficient between the error bound and the averaged empirical errors on the four attacks are larger than 0.9.

Our theoretical results (in Theorems 1 and 2) show that, when an attacker’s reconstruction function has a smaller Lipschitz constant (in the second term), then this attack intrinsically performs better, i.e., more gradient leakage. Note that the second term is often much larger than the first term in the error bound.

Comment#4C: More error bounds on the same gradient leakage attack with different models and architectures. More evaluations across different hyperparameters such as initialization strategies, regularizer strengths.

Response: The main motivation of the paper is to theoretically compare the existing gradient leakage attacks with a unified framework. This provides guidance to compare attacks more fairly and reasonably, as the literature only shows the comparison results at once and in different settings.

We also note the existing attacks do use different models/architectures, and our takeaway is that the Lipschitz of the model/attack algorithm largely determines the attack performance.

In addition, we have tested our error bound with different initializations and we found it is insensitive to them. This is because the unrolled deep neural network learns the intrinsic Lipschitz of the attack algorithm $\mathcal{R}$.

Comment#4D: All experiments should show average behavior for the author's claims to be substantiated (Can the authors provide more experiments like Figure 9c?)

Response: Thanks for your suggestion! The reason we show the best empirical results is to replicate the results shown in the literature. We will add average empirical results as well as the Pearson correlation coefficients.

The reviewer feels this paper is suffering from the problem that even its authors do not know what they want to achieve with their proposed bound. I think this is reflected in all reviewers' scores. I see three options:

• A practical bound used to evaluate practical gradient leakage algorithms. For this, the authors should show that their bound reflects real applications - e.g. the bound is either faster to compute than current evaluations or allows computing of optimal hyperparameters/initialization of the attack. The reviewer feels the current bound is hopeless in achieving both of these things because it is independent of many of the useful attack hyperparameters, it is computationally expensive, and requires unrealistic models to be computed.
• A theoretical bound that closely predicts how the attack behaves on average with respect to a list of parameters of the attack. This can potentially be useful to make generic statements regarding what properties of one attack make it better in one setting or another. The reviewer thinks this is, again, not possible. For this, at least trends need to match, and the time/communication rounds trend presented just does not match real behavior, even by the authors' own admission.
• A theoretical bound that represents worst-case information leakage, which can inform a client how exposed their data is. Here, the fact you use an upper bound on the MSE is problematic.

I will encourage the authors to define in which of these three settings they think their bound operates or define a new one in which the bound application is clear. I also encourage them to clearly outline it in the introduction/abstract of their paper in the next revision.

Comment#1: I understand that relaxing convexity as an assumption can be challenging, and therefore left for future work, but I think the authors agree that this is the ultimate aim of the bound, as presented. However, the techniques used in the proposed bound assume convexity so heavily ( by the author's own admission in non-convex settings, there is even multiple $w^*$ ) that I do not see the used techniques capable of being adapted to a non-convex setting. Further, the statement by the authors above "we should require FL training to converge to the optimal model" is also misguided. If one wants to evaluate privacy risks which is the ultimate goal of gradient leakage attacks the convexity of models and their theoretical or practical convergence properties are immaterial. What matters is whether they get deployed in realistic scenarios or not.

Finally, having $\mathbb{E}||x - \mathcal{R}(w^*)||^2$,as one of your boundary terms and even more so being the smaller term of this said bound, is very counterintuitive when you think about the overall problem here. If a gradient leakage attack already achieves certain MSE in expectation on $w^*$ this is more than good enough lower bound on the privacy lost in an FL process. The rest of the terms ultimately would not matter from a defense point of view. The only reason a client cares about attacks at $w^t$ is that in practice they are stronger. This is not captured by the bound of the authors.

Comment#2: The authors acknowledge that even for their simple models the empirical bound does not decrease with $T$. Their bound does. This suggests their bound is non-predictive of the real behaviour of these attacks. I have stated before this is due to too large overapproximations made by the bound at multiple points, as it is sound. This argues against its use as a theoretical bound used for theoretical analysis

Comment#3A: Do you assume fixed hyperparameters for the attacks and how do you choose them?

Comment#3B: Do you mean to say Figure 9 (a) attacks clients with different numbers of classes from MNIST, when the full federated training is still carried out on full MNIST? This needs to be better explained in the paper.

Comment#3C: I do not understand the provided explanation. Unless I am missing something, each attack doesn't depend on any parameters $\theta_i$. Each $x_i$ is just produced from the previous $x_{i-1}$ by executing for example a single SGD step in the case of InvGrad. Why do you need to optimize any parameters in this scheme? How does the optimized parameter relate to the standard InvGrad?

Comment#4A&D: The authors need to understand that they cannot just promise those results and expect to be accepted on the basis of the current ones. Both of these points are crucial to understand the experimental results they present. Especially for 4A this should be trivial to do and be in a revision of the paper already.

All in all, my worry about the paper's main issues has deepened not resolved after reading the author's responses

We thank the reviewer for the constructive comments and suggestions!

Comment#1: Why is the error bound important if it requires estimating $\mathcal{R}(w^*)$)**? The first term of the bound still depends on the performance at $w^*$ and the leakage algorithm $\mathcal{R}$. Presence of randomness (e.g., from the initialization) also remains as hard as before.

Response: First, under a given convex FL algorithm, the optimal $w^*$ is unique (and can be obtained), and all leakage algorithms are compared using the same optimal model. We observe that, based on this optimal model, all leakage algorithms have relatively stable (variance less than 10) and small reconstruction errors of the first term (though the presence of randomness, e.g., from the initialization). Instead, the existing attacks are tested on intermediate $w^t$, which could cause unstable empirical reconstruction errors, as shown in Figure 1.

Second, we also noticed that the second term largely dominates the error bound, compared with the first one. For instance, in the default setting on MNIST, the two terms in DLG, iDLG, and invGrad, are (30.48, 396.72), (25.25, 341.10), (22.06, 218.28), respectively.

We admit that convex loss may not be satisfied in deep neural networks and generalizing our theoretical results to non-convex losses is important future work.

Comment#2: Discrepancy between practical and bound behavior of leakage attacks with respect to $t$ (both practically and theoretically, the bound predicts that as $t$ increases, the vulnerability of the attacked model increases. This is in stark contradiction with the empirical observations about gradient leakage attacks where exactly the opposite is true)

Response: In most of the results, we found the best empirical errors are very stable with respect to $t$. I guess one possible reason might be that the models used to train the FL are relatively simple (i.e., convex shallow models) and the trend of the model $w^t$ has a certain pattern (e.g., it gradually converges to the optimal model $w^*$). Instead, the existing attacks use nonconvex deep neural networks to train FL, which could memorize the data in the first few iterations, and hence they show less empirical reconstruction error with a small $t$.

Our theoretical results show the error bound decreases w.r.t. $t$. As pointed out by the reviewer, this is due to the error bound in the second term decreasing as $t$ increases.

Comment#3: Unclear or missing implementation details

Comment#3A: what is the average taken over in $\mathbb{E}[x-\mathcal{R}(w^*)]$

Response: The average is over the randomness in $\mathcal{R}$, e.g., different initializations.

Comment#3B: How is $\Gamma$ approximated in practice? How is heterogeneity controlled in general in the experiments provided? Can the authors provide heterogeneity experiments?

Response: Recall $\Gamma = \mathcal{L}^* - p_k \mathcal{L}_k^*$, where $p_k$ can be understood as the fraction of data samples in client $k$ over all clients' data. $\mathcal{L}^*$ is global loss, and $\mathcal{L}_k^*$ is client $k$’s loss, both of which can be calculated under the convex loss setting. In our results, the heterogeneity can be controlled by the number of classes per client. For instance, the clients that have 1 class of data samples show a larger level of heterogeneity than the clients that have 2 classes of data samples—as the client losses in the former case could be more diverse than those in the latter case.

Figure 9(a) demonstrates the results on different levels of heterogeneity. We can see a large level of heterogeneity makes the attack easier, i.e., a lower error bound or empirical error. This is consistent with the existing literature.

Comment#3C: Where are parameters $\theta^i$ coming from in Figure 2 and Algorithm 1? Can you elaborate on why you tune them with layer-wise methods instead of SGD?

Response: Sorry for the confusion. Each $\theta^i$ means the model parameter connecting the $i$-th layer and $i+1$th layer in the unrolled deep neural network. In our context, each $i$-th layer is the intermediate reconstructions $x_i’$ generated by the attack algorithm $\mathcal{R}$. The unrolled deep neural network is to learn $\theta^i$’s via reproducing the intermediate reconstructions $x_i’$. More training details are given in the Appendix C.1.1.

The reason to train the network in a layer-wise fashion is because the number of model parameters is large (e.g., the #parameter in each layer is the #pixels * #pixels). However, we use SGD to update the parameters within each layer-wise training.

We thank the reviewer for appreciating the novelty and the constructive comments!

Comment#1: low correlation between the proposed upper bound Lipschitz Constant and true reconstruction error.

Response: This may be a misunderstanding! Our results show that the best one-snapshot empirical errors are not consistent with the bounded errors in some cases for certain attacks (e.g., InvGrad on FMNUST). However, the error bound per attack indeed has a strong correlation with its empirical errors in expectation. See Figure 9c, where we can see the consistency between the error bounds and average empirical errors.

Comment#2: MSE emphasizes pixel-wise differences are insufficient. It would be beneficial to integrate these non-norm-based metrics such as SSIM and LPIPS.

Response: We agree that structure based SSIM and LPIPS could provide more accurate human perceptual judgment! However, we emphasize this is the first paper to theoretically understand the data reconstruction attack, and we first focus on norm-based metric. Nevertheless, we acknowledge that generalizing our theoretical framework to SSIM or LPIPS face a fundamental challenge: these metrics do NOT even have an analytic form, making the error/similarity bound formulation infeasible.

We thank the reviewer for the constructive comments!

Comment#1: The FL model is required to be strongly convex and smooth, while nonlinear deep neural networks are commonly used in FL.

Response: We emphasize that this is the first work to understand the data reconstruction attack from the theoretical perspective. We note that it is challenging to bound the error in practical FL settings, e.g., non-IID data across clients. To make the problem tractable, we should require FL training to converge to the optimal model, which needs the loss to be convex.

Although deep neural networks do not satisfy this assumption, FL has been also used in convex settings. For instance, the original FL [McMahan et al 2017] uses, e.g., 2-layer ReLu NNs, and we also show theoretical results on the convex 2-layer ReLU networks (Pilanci & Ergen, 2020). We acknowledge it is important future work to generalize our theoretical results to more challenging non-convex losses.

Comment#2: The paper proposes a method to approximately calculate the Lipschitz constant, but there's no guarantee how large the approximation error would be.

Response: It is challenging to bound the approximation error of the estimated Lipschitz constant to the exact one of a highly nonconvex network used in the attacks. Also, our goal in the paper is to design a feasible algorithm to estimate the Lipschitz constant. We admit a better estimation algorithm can lead to a tighter upper bounded Lipschitz constant, which is an interesting future work, but not the focus of the paper. Our results show the estimated Lipschitz constant is stable.

Comment#3: large gap between the upper bound and the attack performance

Response: Note that the derived error bounds consider all randomness in FL training and data reconstruction, and hence they are the worst-case error under such randomness. The empirical attack performance of iDLG (Zhao et al., 2020) and DLG (Zhu et al., 2019) are significantly influenced by initial parameters. As shown in Figure 1, the MSE of DLG could be very large (more than 600), which is close to the upper bound (about 700) in this case. Also shown in Figure 6 and Figure 7, GGL exhibits close upper bound and empirical error.