Understanding Data Reconstruction Leakage in Federated Learning from a Theoretical Perspective

Zifan Wang¹, Binghui Zhang¹, Meng Pang², Yuan Hong³, and Binghui Wang¹
¹Department of Computer Science, Illinois Institute of Technology, USA
²School of Mathematics and Computer Sciences, Nanchang University, China
³School of Computing, University of Connecticut, USA

Abstract

Federated learning (FL) is an emerging collaborative learning paradigm that aims to protect data privacy. Unfortunately, recent works show FL algorithms are vulnerable to the serious data reconstruction attacks. However, existing works lack a theoretical foundation on to what extent the devices’ data can be reconstructed and the effectiveness of these attacks cannot be compared fairly due to their unstable performance. To address this deficiency, we propose a theoretical framework to understand data reconstruction attacks to FL. Our framework involves bounding the data reconstruction error and an attack’s error bound reflects its inherent attack effectiveness. Under the framework, we can theoretically compare the effectiveness of existing attacks. For instance, our results on multiple datasets validate that the iDLG attack inherently outperforms the DLG attack.

1 Introduction

The emerging federated learning (FL) [31] has been a great potential to protect data privacy. In FL, the participating devices keep and train their data locally, and only share the trained models (e.g., gradients or parameters), instead of the raw data, with a center server (e.g., cloud). The server updates its global model by aggregating the received device models, and broadcasts the updated global model to all participating devices such that all devices indirectly use all data from other devices. FL has been deployed by many companies such as Google [15], Microsoft [32], IBM [21], Alibaba [2], and applied in various privacy-sensitive applications, including on-device item ranking [31], content suggestions for on-device keyboards [6], next word prediction [27], health monitoring [38], and medical imaging [23].

Refer to caption — Figure 1: Impact of the initial parameters of a Gaussian distribution on the DRA performance. a (b) in the x-axis indicates the mean (standard deviation) of the Gaussian. The default mean and standard deviation are both 1.

Unfortunately, recent works show that, though only sharing device models, it is still possible for an adversary (e.g., malicious server) to perform the severe data reconstruction attack (DRA) to FL [57], where an adversary could directly reconstruct the device’s training data via the shared device models. Later, a bunch of follow-up enhanced attacks [20, 45, 55, 51, 47, 53, 22, 56, 9, 3, 30, 11, 43, 48, 18, 49, 35]) are proposed by either incorporating (known or unrealistic) prior knowledge or requiring an auxiliary dataset to simulate the training data distribution.

However, we note that existing DRA methods have several limitations: First, they are sensitive to the initialization (which is also observed in [47]). For instance, we show in Figure 1 that the attack performance of iDLG [55] and DLG [57] are significantly influenced by initial parameters (i.e., the mean and standard deviation) of a Gaussian distribution, where the initial data is sampled from. Second, existing DRAs mainly show comparison results on a FL model at a snapshot, which cannot reflect attacks’ true effectiveness. As FL training is dynamic, an adversary can perform attacks in any stage of the training. Hence, Attack A shows better performance than Attack B at a snapshot does not imply A is truly more effective than B. Third, worse still, they lack a theoretical understanding on to what extent the training data can be reconstructed. These limitations make existing DRAs cannot be easily and fairly compared and hence it is unknown which attacks are inherently more effective.

In this paper, we aim to bridge the gap and propose a theoretical framework to understand DRAs to FL. Specifically, our framework aims to bounds the error between the private data and the reconstructed counterpart in the whole FL training, where an attack’s (smaller) error bound reflects its inherent (better) attack effectiveness. Our theoretical results show that when an attacker’s reconstruction function has a smaller Lipschitz constant, then this attack intrinsically performs better. Under the framework, we can theoretically compare the existing DRAs by directly comparing their bounded errors. We test our framework on multiple state-of-the-art attacks and benchmark datasets. For example, our results show that InvGrad [13] performs better than DLG [57] and iDLG [55] on complex datasets, while iDLG is comparable or performs slightly better than DLG.

2 Related Work

Existing DRAs to FL are roughly classified as optimization based and close-form based.

Optimization-based DRAs to FL: A series of works [20, 57, 45, 55, 47, 53, 22, 9, 3, 11, 48, 30] formulate DRAs as the gradient matching problem, i.e., an optimization problem that minimizes the difference between gradient from the raw data and that from the reconstructed counterpart. Some works found the gradient itself includes insufficient information to well recover the data [22, 56]. For example, [56] show there exist pairs of data (called twin data) that visualize different, but have the same gradient. To mitigate this issue, a few works propose to incorporate prior knowledge (e.g., total variation (TV) regularization [13, 53], batch normalization (BN) statistics [53]) into the training data, or introduce an auxiliary dataset to simulate the training data distribution [20, 45, 22] (e.g., via generative adversarial networks (GANs) [14]). Though empirically effective, these methods are less practical or data inefficient, e.g., TV is limited to natural images, BN statistics are often unavailable, and training an extra model (e.g., GAN [14]) requires a large amount of data samples.

Closed-form DRAs to FL: A few recent works [13, 56, 11] derive closed-form solutions to reconstruct data, but they require the neural network used in the FL algorithm be fully connected [13], linear/ReLU [11], or convolutional [56].

We will design a framework to theoretically understand the DRA to FL in a general setting, and provide a way to compare the effectiveness of existing DRAs.

3 Preliminaries and Problem Setup

3.1 Federated Learning (FL)

The FL paradigm enables a server to coordinate the training of multiple local devices through multiple rounds of global communications, without sharing the local data. Suppose there are $N$ devices and a central server participating in FL. Each $k$ -th device owns a training dataset ${D}^{k}=\{(\mathbf{x}_{j}^{k},y_{j}^{k})\}_{j=1}^{n_{k}}$ with $n_{k}$ samples, and each sample $\mathbf{x}_{j}^{k}$ has a label $y_{j}^{k}$ . FL considers the following distributed optimization problem:

\displaystyle\min_{{\bf w}}\mathcal{L}({\bf w})=\sum\nolimits_{k=1}^{N}p_{k}\mathcal{L}_{k}({\bf w}),

(1)

where $p_{k}\geq 0$ is the weight of the $k$ -th device and $\sum_{k=1}^{N}p_{k}=1$ ; the $k$ -th device’s local objective is defined by $\mathcal{L}_{k}({\bf w})=\frac{1}{n_{k}}\sum_{j=1}^{n_{k}}\ell({\bf w};({\bf x}_{j}^{k},y_{j}^{k}))$ , with $\ell(\cdot;\cdot)$ an algorithm-dependent loss function.

FedAvg [31]: It is the de factor FL algorithm to solve Equation (1) in an iterative way. In each communication round, each $k$ -th device only shares the gradients $\nabla_{\bf w}\mathcal{L}_{k}({\bf w})$ instead of the raw data ${D}^{k}$ to the server. Specifically, in the current round $t$ , each $k$ -th device first downloads the latest global model (denoted as ${\bf w}_{t-1}$ ) from the server and initializes its local model as ${\bf w}^{k}_{t}={\bf w}_{t-1}$ ; then it performs (e.g., $E$ ) local SGD updates as below:

\displaystyle{\bf w}^{k}_{t+j}\leftarrow{\bf w}^{k}_{t+j-1}-\eta_{t+j}

\displaystyle\nabla\mathcal{L}_{i}({\bf w}^{k}_{t+j};\xi_{t+j}^{k}),j=1,\cdots,E

(2)

where $\eta_{t+j}$ is the learning rate and $\xi_{t+j}^{k}$ is sampled from the local data ${D}^{k}$ uniformly at random.

Next, the server updates the global model ${\bf w}_{t}$ by aggregating full or partial device models. The final global model, i.e., ${\bf w}_{T}$ , is downloaded by all devices for their learning tasks.

•

Full device participation. It requires all device models for aggregation, and the server performs ${\bf w}_{t}\>\leftarrow\>\sum_{k=1}^{N}p_{k}\,{\bf w}_{t}^{k}$ with $p_{k}=\frac{n_{k}}{\sum_{i=1}^{N}n_{i}}$ and ${\bf w}^{k}_{t}={\bf w}^{k}_{t+E}$ . This means the server must wait for the slowest devices, which is often unrealistic in practice.
•

Partial device participation. This is a more realistic setting as it does not require the server to know all device models. Suppose the server only needs $K$ ( $<N$ ) device models for aggregation and discards the remaining ones. Let ${\mathcal{S}}_{t}$ be the set of $K$ chosen devices in the $t$ -th iteration. Then, the server’s aggregation step performs ${\bf w}_{t}\>\leftarrow\>\frac{N}{K}\sum_{k\in{\mathcal{S}}_{t}}p_{k}\,{\bf w}_{t}^{k}$ with ${\bf w}^{k}_{t}={\bf w}^{k}_{t+E}$ .

Quantifying the degree of non-IID (heterogeneity): Real-world FL applications often do not satisfy the IID assumption for data among local devices. [28] proposed a way to quantify the degree of non-IID. Specifically, let $\mathcal{L}^{*}$ and $\mathcal{L}_{k}^{*}$ be the minimum values of $\mathcal{L}$ and $\mathcal{L}_{k}$ , respectively. Then, the term $\Gamma=\mathcal{L}^{*}-\sum_{k=1}^{N}p_{k}\mathcal{L}_{k}^{*}$ is used for quantifying the non-IID. If the data are IID, then $\Gamma$ goes to zero as the number of samples grows. If the data are non-IID, then $\Gamma$ is nonzero, and its magnitude reflects the heterogeneity of the data distribution.

3.2 Optimization-based DRAs to FL

Existing DRAs assume an honest-but-curious server, i.e., the server has access to all device models in all communication rounds, follows the FL protocol, and aims to infers devices’ private data. Given the private data ${\bf x}\in[0,1]^{d}$ with private label $y$ ¹¹1This can be a single data sample or a batch of data samples., we denote the reconstructed data by a malicious server as $(\hat{{\bf x}},\hat{y})=\mathcal{R}({\bf w}_{t})$ , where $\mathcal{R}(\cdot)$ indicates a data reconstruction function, and ${\bf w}_{t}$ can be any intermediate global model.

Modern optimization-based DRAs use different $\mathcal{R}(\cdot)$ , but majorly base on gradient matching. Specifically, they solve the optimization problem:

\displaystyle(\hat{{\bf x}},\hat{y})=\mathcal{R}({\bf w}_{t})=\arg\min_{{\bf x}^{\prime}\in[0,1]^{d},y^{\prime}}\textrm{GML}(g_{{\bf w}_{t}}({\bf x},y),g_{{\bf w}_{t}}({\bf x}^{\prime},y^{\prime}))+\lambda\textrm{Reg}({\bf x}^{\prime})

(3)

where we denote the gradient of loss w.r.t. $({\bf x},y)$ be $g_{{\bf w}_{t}}({\bf x},y)=\nabla_{\bf w}\mathcal{L}({\bf w}_{t};({\bf x},y))$ for notation simplicity. $\textrm{GML}(\cdot,\cdot)$ means the gradient matching loss (i.e., the distance between the real gradients and estimated gradients) and $\textrm{Reg}(\cdot)$ is an auxiliary regularizer for the reconstruction. Here, we list $\textrm{GML}(\cdot,\cdot)$ and $\textrm{Reg}(\cdot)$ for three representative DRAs, and more attacks are shown in Appendix D.2.

•

DLG [57] uses mean squared error as the gradient matching loss, i.e., $\textrm{GML}(g_{{\bf w}_{t}}({\bf x},y),\\ g_{{\bf w}_{t}}({\bf x}^{\prime},y^{\prime}))=\|g_{{\bf w}_{t}}({\bf x},y)-g_{{\bf w}_{t}}({\bf x}^{\prime},y^{\prime})\|_{2}^{2}$ and uses no regularizer.
•

iDLG [55] estimates the label $y$ before solving Equation (3). Assuming the estimated label is $\hat{y}$ , iDLG solves $\hat{{\bf x}}=\arg\min_{{\bf x}^{\prime}}{\mathbb{E}}_{\bf x}[\textrm{GML}(g_{{\bf w}_{t}}({\bf x},y),g_{{\bf w}_{t}}({\bf x}^{\prime},\hat{y}))+\lambda\textrm{Reg}({\bf x}^{\prime})]$ , where it uses the same $\textrm{GML}(\cdot)$ as DLG and also has no regularizer.
•

InvGrad [13] improves upon DLG and iDLG. It first estimates the private label as $\hat{y}$ in advance. Then it uses a negative cosine similarity as $\textrm{GML}(\cdot)$ and a total variation regularizer $\textrm{Reg}_{\textrm{TV}}(\cdot)$ as an image prior. Specifically, InvGrad solves for $\hat{{\bf x}}=\arg\min_{{\bf x}^{\prime}}{\mathbb{E}}_{\bf x}[1-\frac{\langle g_{{\bf w}_{t}}({\bf x},y),g_{{\bf w}_{t}}({\bf x}^{\prime},\hat{y})\rangle}{\|g_{{\bf w}_{t}}({\bf x},y)\|_{2}\cdot\|g_{{\bf w}_{t}}({\bf x}^{\prime},\hat{y}\|_{2}}+\lambda\textrm{Reg}_{\textrm{TV}}({\bf x}^{\prime})]$ .

Algorithm 1 shows the pseudo-code of iterative solvers for DRAs and Algorithm 4 in Appendix shows more details for each attack. As the label $y$ can be often accurately inferred, we now only consider reconstructing the data ${\bf x}$ for notation simplicity. Then, the attack performance is measured by the similarity $\textrm{sim}(\hat{\bf x},{\bf x})$ between $\hat{\bf x}$ and ${\bf x}$ . The larger similarity, the better attack performance. In the paper, we use the common similarity metric, i.e., the negative mean-square-error $\textrm{sim}(\hat{\bf x},{\bf x})=-\mathbb{E}\|\hat{\bf x}-{\bf x}\|^{2}$ , where the expectation $\mathbb{E}$ considers the randomness during reconstruction.

1 Input: Model parameters

{\bf w}_{t}

; true gradient

g({\bf x},y)

;

\eta,\lambda

2Output: Reconstructed data

\hat{\bf x}

31: Initialize dummy input(s)

{\bf x}_{0}^{\prime}

from a Gaussian distribution, and dummy label(s)

y_{0}^{\prime}

42: for

i=0;i<I;i++

53:

\textrm{L}({\bf x}_{i}^{\prime})=\textrm{GML}(g_{{\bf w}_{t}}({\bf x},y),g_{{\bf w}_{t}}({\bf x}_{i}^{\prime},y_{i}^{\prime}))+\lambda\textrm{Reg}({\bf x}_{i}^{\prime})

64:

{\bf x}_{i+1}^{\prime}\leftarrow\textrm{SGD}({\bf x}_{i}^{\prime};{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\theta^{i}})={\bf x}_{i}^{\prime}-\eta\nabla_{{\bf x}_{i}^{\prime}}\textrm{L}({\bf x}_{i}^{\prime})

{\bf x}_{i+1}^{\prime}=\textrm{Clip}({{\bf x}_{i+1}^{\prime},0,1})

76: end for

7: return

{\bf x}_{I}^{\prime}

Algorithm 1 Iterative solvers for optimization-based data reconstruction attacks

4 A Theoretical Framework to Understand DRAs to FL

Though many DRAs to FL have been proposed, it is still unknown how to theoretically compare the effectiveness of existing attacks, as stated in Introduction. In this section, we understand DRAs to FL from a theoretical perspective. We first derive a reconstruction error bound for convex objective losses. The error bound involves knowing the Lipschitz constant of the data reconstruction function. Directly calculating the exact Lipschitz constant is computationally challenging. We then adapt existing methods to calculate its upper bound. We argue that an attack with a smaller upper bound is intrinsically more effective. We also emphasize our theoretical framework is applicable to any adversary who knows the global model during FL training (see below Theorem 1 and Theorem 2).

4.1 Bounding the Data Reconstruction Error

Give random data ${\bf x}$ from a device, our goal is to bound the common norm-based reconstruction error²²2The norm-based mean-square-error (MSE) bound can be easily generalized to the respective PSNR bound. This is because PSNR = -10 log (MSE). However, it is unable to generalize to SSIM or LPIPS since these metrics do not have an analytic form., i.e., $\mathbb{E}\|\mathbf{x}-\mathcal{R}({\bf w}_{t})\|^{2}$ at any round $t$ , where $\mathcal{R}(\cdot)$ can be any DRA and the expectation considers the randomness in $\mathcal{R}(\cdot)$ , e.g., due to different initializations. Directly bounding this error is challenging because the global model dynamically aggregates local device models, which are trained by a (stochastic) learning algorithm and whose learning procedure is hard to characterize during training. To alleviate this issue, we introduce the optimal global model ${\bf w}^{\star}$ that can be learnt by the FL algorithm. Then, we can bound the error as follows:

	$\displaystyle\mathbb{E}\\|\mathbf{x}-\mathcal{R}({\bf w}_{t})\\|^{2}$	$\displaystyle=\mathbb{E}\\|\mathbf{x}-\mathcal{R}({\bf w}^{\star})+\mathcal{R}({\bf w}^{\star})-\mathcal{R}({\bf w}_{t})\\|^{2}$
		$\displaystyle\leq 2\big{(}\mathbb{E}\\|\mathbf{x}-\mathcal{R}({\bf w}^{\star})\\|^{2}+\mathbb{E}\\|\mathcal{R}({\bf w}^{\star})-\mathcal{R}({\bf w}_{t})\\|^{2}\big{)}.$		(4)

Note that the first term in Equation (4) is a constant and can be directly computed under a given reconstruction function $\mathcal{R}(\cdot)$ and a convex loss used in FL. Specifically, if the loss in each device is convex, the global model can converge to the optimal ${\bf w}^{*}$ based on theoretical results in [28]. Then we can obtain $\mathcal{R}({\bf w}^{*})$ per attack and compute the first term. In our experiments, we run the FL algorithm until the loss difference between two consecutive iterations is less than $1e{-5}$ , and treat the final global model as ${\bf w}^{*}$ .

Now our goal reduces to bounding the second term. However, it is still challenging without knowing any property of the reconstruction function $\mathcal{R}(\cdot)$ . In practice, we note $\mathcal{R}(\cdot)$ is often Lipschitz continuous, which can be verified later.

Proposition 1.

$\mathcal{R}(\cdot)$ is $L_{\mathcal{R}}$ -Lipschitz continuous: there exists a constant $L_{\mathcal{R}}$ such that $\|\mathcal{R}({\bf v})-\mathcal{R}({\bf w})\|\leq L_{\mathcal{R}}\|{\bf v}-{\bf w}\|,\forall{\bf v},{\bf w}$ . The smallest $L_{\mathcal{R}}$ is called the Lipschitz constant.

Next, we present our theoretical results and their proofs are seen in Appendix B and Appendix C, respectively. Note that our error bounds consider all randomness in FL training and data reconstruction.

Theoretical results with full device participation:

We first analyze the case where all devices participate in the aggregation on the server in each communication round. Assume the FedAvg algorithm stops after $T$ iterations and returns ${\bf w}_{T}$ as the solution. Let $L,\mu,\sigma_{k},G$ be defined in Assumptions 1-4 (more details in Appendix A) and $L_{\mathcal{R}}$ be defined in Proposition 1.

Theorem 1.

Let Assumptions 1-4 hold. Choose $\gamma=\max\{8L/\mu,E\}$ and the learning rate $\eta_{t}=\frac{2}{\mu(\gamma+t)}$ . Let $B=\sum_{k=1}^{N}p_{k}^{2}\sigma_{k}^{2}+6L\Gamma+8(E-1)^{2}G^{2}$ . Then, for any round $t$ , FedAvg with full device participation satisfies

\displaystyle\mathbb{E}\|\mathbf{x}-\mathcal{R}({\bf w}_{t})\|^{2}\leq 2\mathbb{E}\|\mathbf{x}-\mathcal{R}({\bf w}^{\star})\|^{2}+\frac{2L_{\mathcal{R}}^{2}}{\gamma+t}\Big{(}\frac{4B}{\mu^{2}}+(\gamma+1){\mathbb{E}}\|{\bf w}_{1}-{\bf w}^{*}\|^{2}\Big{)}.

(5)

Theoretical results with partial device participation:

As discussed in Section 3, partial device participation is more practical. Recall that ${\mathcal{S}}_{t}$ contains the $K$ active devices in the $t$ -th iteration. To show our theoretical results, we require the $K$ devices in ${\mathcal{S}}_{t}$ are selected from a distribution (e.g., $p_{1},p_{2},\cdots,p_{N}$ ) independently and with replacement, following [39, 28]. Then FedAvg performs aggregation as ${\bf w}_{t}\leftarrow\frac{1}{K}\sum_{k\in{\mathcal{S}}_{t}}{\bf w}_{t}^{k}$ .

Theorem 2.

Let Assumptions 1-4 hold. Let $\gamma$ , $\eta_{t}$ , and $B$ be defined in Theorem 1, and define $C=\frac{4}{K}E^{2}G^{2}$ . For any round $t$ , FedAvg with ${\mathcal{S}}_{t}$ device participation satisfies

\displaystyle\mathbb{E}\|\mathbf{x}-\mathcal{R}({\bf w}_{t})\|^{2}\leq 2\mathbb{E}\|\mathbf{x}-\mathcal{R}({\bf w}^{\star})\|^{2}+\frac{2L_{\mathcal{R}}^{2}}{\gamma+t}\Big{(}\frac{4(B+C)}{\mu^{2}}+(\gamma+1){\mathbb{E}}\|{\bf w}_{1}-{\bf w}^{*}\|^{2}\Big{)}.

(6)

4.2 Computing the Lipschitz Constant for Data Reconstruction Functions

We show how to calculate the Lipschitz constant for data reconstruction function. Our idea is built upon the strong connection between optimizing DRAs and the corresponding unrolled deep networks; and then adapt existing methods to approximate the Lipschitz upper bound.

Iterative solvers for optimization-based DRAs as unrolled deep feed-forward networks: Recent works [7, 29, 34] show a strong connection between iterative algorithms and deep network architectures. The general idea of algorithm unrolling is: starting with an abstract iterative algorithm, we map one iteration into a single network layer, and stack a finite number of (e.g., $H$ ) layers to form a deep network, which is also called unrolled deep network. Feeding the data through an $H$ -layer network is hence equivalent to executing the iterative algorithm $H$ iterations. The parameters of the unrolled networks are learnt from data by training the network in an end-to-end fashion. From Algorithm 1, we can see the trajectory of an iterative solver for an optimization-based DRA corresponds to a customized unrolled deep feed-forward network. Specifically, we treat the initial ${\bf x}_{0}^{\prime}$ (and ${\bf w}_{t}$ ) as the input, the intermediate reconstructed ${\bf x}_{i}^{\prime}$ as the $i$ -th hidden layer, followed by a clip nonlinear activation function, and the final reconstructed data $\hat{\bf x}={\bf x}_{I}^{\prime}$ as the output of the network. Given intermediate $\{{\bf x}^{\prime}_{i}\}$ with a set of data samples, we can train parameterized deep feed-forward networks (universal approximation) to fit them, e.g., via the greedy layer-wise training strategy [5], where each $\theta^{i}$ means the model parameter connecting the $i$ -th layer and $i+1$ -th layer. Figure 2 visualizes the unrolled deep feed-forward network for the optimization-based DRA.

Definition 1 (Deep Feed-Forward Network).

An $H$ -layer feed-forward network is an function $T_{MLP}({\bf x})=f_{H}\circ\rho_{H-1}\circ\cdots\circ\rho_{1}\circ f_{1}({\bf x})$ , where $\forall h$ , the $h$ -th hidden layer $f_{h}:{\bf x}\mapsto{\bf M}_{h}{\bf x}+b_{h}$ is an affine function and $\rho_{h}$ is a non-linear activation function.

Upper bound Lipschitz computation: [44] showed that computing the exact Lipschitz constant for deep (even 2-layer) feed-forward networks is NP-hard. Hence, they resort to an approximate computation and propose a method called AutoLip to obtain an upper bound of the Lipschitz constant. AutoLip relies on the concept of automatic differentiation [16], a principled approach that computes differential operators of functions from consecutive operations through a computation graph. When the operations are all locally Lipschitz-continuous and their partial derivatives can be computed and maximized, AutoLip can compute the Lipschitz upper bound efficiently. Algorithm 2 shows the details of AutoLip.

With Autolip, [44] showed that a feed-forward network with 1-Lipschitz activation functions has an upper bounded Lipschitz constant below.

Lemma 1.

For any $H$ -layer feed-forward network with $1$ -Lipschitz activation functions, the AutoLip upper bound becomes $L_{AutoLip}=\prod_{h=1}^{H}\|{\bf M}_{h}\|_{2}$ , where ${\bf M}_{h}$ is defined in Definition 1.

Note that a matrix $\ell_{2}$ -norm equals to its largest singular value, which could be computed efficiently via the power method [33]. More details are shown in Algorithm 3 (A better estimation algorithm can lead to a tighter upper bounded Lipschitz constant). Obviously, the used Clip activation function is 1-Lipschitz. Hence, by applying Lemma 1 to the optimization-based DRAs, we can derive an upper bounded Lipschitz $L_{\mathcal{R}}$ .

0: function

f

and its computation graph

(g_{1},...,g_{H})

0: Lipschitz upper bound

L_{AutoLip}\geq L_{f}

11:

\phi_{0}({\bf x})={\bf x}

;

\phi_{h}({\bf x})=f({\bf x})

22:

\phi_{h}({\bf x})=g_{h}({\bf x},\phi_{1}({\bf x}),\cdots,\phi_{h-1}({\bf x})),\forall h\in[1,H]

\mathcal{Z}=\{(z_{0},...,z_{H})~{}:~{}\forall h\in[0,H],\phi_{h}\mbox{ is constant}\Rightarrow z_{h}=\phi_{h}(0)\}

L_{0}\leftarrow 1

5: for

h=1

H

do 6:

L_{h}\leftarrow\sum\limits_{i=1}^{h-1}\max\limits_{z\in\mathcal{Z}}\|\partial_{i}g_{h}(z)\|_{2}L_{i}

7: end for 8: return

L_{AutoLip}=L_{H}

Algorithm 2 AutoLip

0: affine function

f:{\bf R}^{n}\rightarrow{\bf R}^{m}

, #iterations

Iter

0: Upper bound of the Lipschitz constant

L_{f}

1: for

j=1

Iter

do 2:

v\leftarrow\nabla g(v)

where

g(x)=\frac{1}{2}\|f(x)-f(0)\|_{2}^{2}

\lambda\leftarrow\|v\|_{2}

v\leftarrow v/\lambda

5: end for 6: return

L_{f}=\|f(v)-f(0)\|_{2}

Algorithm 3 Power method to calculate the matrix

\ell_{2}

-norm

5 Evaluation

Table 1: Best empirical errors (log scale) of the four baseline attacks on the three datasets in the default setting.

Data/Algorithm	Fed. $\ell_{2}$ -LogReg: single				Fed. 2-LinConvNet: single				Fed. $\ell_{2}$ -LogReg: batch
Data/Algorithm	DLG	iDGL	InvGrad	GGL	DLG	iDGL	InvGrad	GGL	DLG	iDGL	InvGrad	GGL
MNIST	3.48	3.38	3.09	3.14	3.69	3.50	3.42	3.29	6.38	6.28	6.08	4.94
FMNIST	3.54	3.42	3.35	3.25	3.84	3.58	3.52	3.13	6.44	6.35	6.29	4.98
CIFAR10	4.32	4.13	4.13	3.92	4.52	3.37	4.33	3.70	6.46	6.45	6.63	5.31

5.1 Experimental Setup

Datasets and models: We conduct experiments on three benchmark image datasets, i.e., MNIST [25], Fashion-MNIST (FMNIST) [50], and CIFAR10 [24]. We examine our theoretical results on the FL algorithm that uses the $\ell_{2}$ -regularized logistic regression ( $\ell_{2}$ -LogReg) and the convex 2-layer linear convolutional network (2-LinConvNet) [37], since their loss functions satisfy Assumptions 1-4. In the experiments, we evenly distribute the training data among the $N$ devices. Based on this setting, we can calculate $L,\mu,\sigma_{k}$ , and $G$ used in our theorems, respectively. In addition, we can compute the Lipschitz constant $L_{\mathcal{R}}$ via the unrolled feed-forward network. These values together are used to compute the upper bound of our Theorems 1 and 2. More details about the two algorithms, the unrolled feed-forward network, and the calculation of these parameter values are shown in Appendix D.

Attack baselines: We test our theoretical results on four optimization-based data reconstruction attacks, i.e., DLG [57], iDLG [55], InvGrad [13], and GGL [30]. The algorithms and descriptions of these attacks are deferred to Appendix D. We test these attacks on recovering both the single image and a batch of images in each device.

Parameter setting: Several important hyperparameters in the FL training (i.e., federated $\ell_{2}$ -LogReg or federated 2-LinConvNet) that would affect our theoretical results: the total number of devices $N$ , the total number of global rounds $T$ , and the number of local SGD updates $E$ . By default, we set $T=100$ and $E=2$ . We set $N=10$ on the three datasets for the single image recovery, while set $N=15,10,5$ on the three datasets for the batch images recovery, considering their different difficulty levels. we consider full device participation. When studying the impact of these hyperparameters, we fix others as the default value.

5.2 Experimental Results

In this section, we test the upper bound reconstruction error by our theoretical results for single image and batch images recovery. We also show the average (across 10 iterations) reconstruction errors that are empirically obtained by the baseline DRAs with different initializations. The best possible (one-snapshot) empirical results of baseline attacks are reported in Table 1.

5.2.1 Results on single image recovery

Figure 3-Figure 8 show the single image recovery results on the three datasets and two FL algorithms, respectively. We have several observations. First, iDLG has smaller upper bound errors than DLG, indicating iDLG outperforms DLG intrinsically. One possible reason is that iDLG can accurately estimate the labels, which ensures data reconstruction to be more stable. Such a stable reconstruction yields a smaller Lipschitz $L_{\mathcal{R}}$ , and thus a smaller upper bound in Theorem 1. InvGrad is on top of iDLG and adds a TV regularizer, and obtains smaller error bounds than iDLG. This implies the TV prior can help stabilize the data reconstruction and hence is beneficial for reducing the error bounds. Note that the error bounds of these three attacks are (much) larger than the average empirical errors, indicating there is still a gap between empirical results and theoretical results. Further, GGL has (much) smaller bounded errors than DLG, iDLG, and InvGrad. This is because GGL trains an encoder on the whole dataset to learn the image manifold, and then uses the encoder for data reconstruction, hence producing smaller $L_{\mathcal{R}}$ . In Figure 3(b), we observe its bounded error is close to the empirical error. For instance, we calculate that the estimated $L_{\mathcal{R}}$ for the DLG, iDLG, InvGrad, and GGL attacks in the default setting on MNIST are 22.17, 20.38, 18.43, and 13.36, respectively.

Second, the error bounds are consistent with the average empirical errors, validating they have a strong correlation. Particularly, we calculate the Pearson correlation coefficients between the error bound and the averaged empirical error on these attacks in all settings are $>0.9$ .

Third, the error bounds do not consistent correlations with the best empirical errors. For instance, we can see GGL has lower error bounds than InvGrad on $\ell_{2}$ -LogReg, but its best empirical error is larger than InvGrad on MNIST (3.14 vs 3.09). Similar observations on CIFAR10 on federated 2-LinConvNet, where InvGrad’s error bound is smaller than iDLG’s, but its best empirical error is larger (4.33 vs 3.37). More details see Table 1. The reason is that the reported empirical errors are the best possible one-snapshot results with a certain initialization, which do not reflect the attacks’ inherent effectiveness. Recall in Figure 1 that empirical errors obtained by these attacks could be sensitive to different initializations. In practice, the attacker may need to try many initializations (which could be time-consuming) to obtain the best empirical error.

Impact of $E$ , $N$ , and $T$ : When the local SGD updates $E$ and the number of total clients $N$ increase, the upper bound error also increases. This is because a large $E$ and $N$ will make FL training unstable and hard to converge, as verified in [28]. On the other hand, a larger total number of global rounds $T$ tends to produce a smaller upper bounded error. This is because a larger $T$ stably makes FL training closer to the global optimal under the convex loss.

5.2.2 Results on batch images recovery

Figures 9-11 show the results of batch images recovery on the three image datasets. As federated 2-LinConvNet has similar trends, we only show federated $\ell_{2}$ -LogReg results for simplicity. First, similar to results on single image recovery, GGL performs the best; InvGrad outperforms iDLG, which outperforms DLG both empirically and theoretically. Moreover, a larger $E$ and $N$ incur larger upper bound error, while a larger $T$ generates smaller upper bound error. Second, both empirical errors and upper bound errors for batch images recovery are much larger than those for single image recovery. This indicates that batch images recovery are more difficult than single image recovery, as validated in many existing works such as [13, 53].

6 Discussion

First term vs second term in the error bound: We calculate the first term and second term of the error bound in our theorem in the default setting. The two terms in DLG, iDLG, InvGrad, and GGL on MNIST are (30.48, 396.72), (25.25, 341.10), (22.06, 218.28), and (20.21, 29.13) respectively. This implies the second term dominates the error bound.

Error bounds vs. degree of non-IID: The non-IID of data across clients can be controlled by the number of classes per client—small number indicates a larger degree of non-IID. Here, we tested #classes=2, 4, 6, 8 on MNIST and the results are shown in Figure 12a. We can see the bounded errors are relatively stable vs. #classes on DLG, iDLG, and GGL, while InvGrad has a larger error as the #classes increases. The possible reason is that DLG and iDLG are more stable than InvGrad, which involves a more complex optimization.

Error bounds vs. batch size: Our batch results use a batch size 20. Here, we also test batch size=10, 15, 25, 30 and results are in Figure 12b. We see bounded errors become larger with larger batch size. This is consistent with existing observations [13] on empirical evaluations.

Error bounds on closed-form DRAs: Our theoretical results can be also applied in closed-form attacks. Here, we choose the Robbing attack [11] for evaluation and its details are in Appendix D.2. The results for single image and batch images recovery on the three datasets and two FL algorithms are shown in Figures 13, 14, and 15, respectively. We can see Robbing obtains both small empirical errors and bounded errors (which are even smaller than GGL). This is because its equation solving is suitable to linear layers, and hence relatively accurate on the federated $\ell_{2}$ -LogReg and federated 2-LinConvNet models.

Practical use of our error bound: Our error bound has several benefits in practice. First, it can provide guidance or insights to attackers, e.g., the attack performance can be estimated with our error bound prior to the attacks. Then, attackers can make better decisions on the attacks, e.g., try to improve the attack beyond the worst-case bound (using different settings), choose to not perform the attack if the estimated error is too high. Second, it can understand the least efforts to guide the defense design, e.g., when we pursue a minimum obfuscation of local data/model (maintain high utility) and minimum defense based on the worst-case attack performance sometimes could be acceptable in practice.

Defending against DRAs: Various defenses have been proposed against DRAs [46, 57, 43, 12, 26, 17, 19]. However, there are two fundamental limitations in existing defenses: First, empirical defenses are soon broken by stronger/adaptive attacks [8, 40, 4]. Second, provable defenses based on differential privacy (DP) [10, 1, 52, 17, 19]) incur significant utility losses to achieve reasonable defense performance since the design of such randomization-based defenses did not consider specific inference attacks. Vert recently, [35] proposed an information-theoretical framework to learn privacy-preserving representations against DRAs, and showed better utility than DP-SGD [1, 17] under close privacy performance. It is interesting future work to incorporate information-theoretical privacy into FL to prevent data reconstruction.

7 Conclusion

Federated learning (FL) is vulnerable to data reconstruction attacks (DRAs). Existing attacks mainly enhance the empirical attack performance, but lack a theoretical understanding. We study DRAs to FL from a theoretical perspective. Our theoretical results provide a unified way to compare existing attacks theoretically. We also validate our theoretical results via evaluations on multiple datasets and baseline attacks. Future works include: 1) designing better or adapting existing Lipschitz estimation algorithms to obtain tighter error bounds; 2) generalizing our theoretical results to non-convex losses; 3) designing theoretically better DRAs (i.e., with smaller Lipschitz) as well as effective defenses against the attacks (i.e., ensuring larger Lipschitz of their reconstruction function), inspired by our framework; and 4) developing effective provable defenses against DRAs.

References

[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In CCS, 2016.
[2] Alibaba Federated Learning. https://federatedscope.io/, 2022.
[3] Mislav Balunovic, Dimitar Iliev Dimitrov, Robin Staab, and Martin Vechev. Bayesian framework for gradient leakage. In ICLR, 2022.
[4] Mislav Balunovic, Dimitar Iliev Dimitrov, Robin Staab, and Martin Vechev. Bayesian framework for gradient leakage. In ICLR, 2022.
[5] Yoshua Bengio, Pascal Lamblin, Dan Popovici, and Hugo Larochelle. Greedy layer-wise training of deep networks. NeurIPS, 2006.
[6] Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konevcnỳ, Stefano Mazzocchi, H Brendan McMahan, Timon Van Overveldt, David Petrou, Daniel Ramage, and Jason Roselander. Towards federated learning at scale: System design. MLSys, 2019.
[7] Xiaohan Chen, Jialin Liu, Zhangyang Wang, and Wotao Yin. Theoretical linear convergence of unfolded ista and its practical weights and thresholds. In NeurIPS, 2018.
[8] Christopher A Choquette-Choo, Florian Tramer, Nicholas Carlini, and Nicolas Papernot. Label-only membership inference attacks. In ICML, 2021.
[9] Trung Dang, Om Thakkar, Swaroop Ramaswamy, Rajiv Mathews, Peter Chin, and Franccoise Beaufays. Revealing and protecting labels in distributed training. NeurIPS, 2021.
[10] Cynthia Dwork. Differential privacy. In ICALP, 2006.
[11] Liam H Fowl, Jonas Geiping, Wojciech Czaja, Micah Goldblum, and Tom Goldstein. Robbing the fed: Directly obtaining private data in federated learning with modified models. In ICLR, 2022.
[12] Wei Gao, Shangwei Guo, Tianwei Zhang, Han Qiu, Yonggang Wen, and Yang Liu. Privacy-preserving collaborative learning with automatic transformation search. In CVPR, 2021.
[13] Jonas Geiping, Hartmut Bauermeister, Hannah Dröge, and Michael Moeller. Inverting gradients–how easy is it to break privacy in federated learning? In NeurIPS, 2020.
[14] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In NeurIPS, 2014.
[15] Google Federated Learning. https://federated.withgoogle.com/, 2022.
[16] Andreas Griewank and Andrea Walther. Evaluating derivatives: principles and techniques of algorithmic differentiation. SIAM, 2008.
[17] Chuan Guo, Brian Karrer, Kamalika Chaudhuri, and Laurens van der Maaten. Bounding training data reconstruction in private (deep) learning. In International Conference on Machine Learning, pages 8056–8071. PMLR, 2022.
[18] Niv Haim, Gal Vardi, Gilad Yehudai, Ohad Shamir, and Michal Irani. Reconstructing training data from trained neural networks. In NeurIPS, 2022.
[19] Jamie Hayes, Borja Balle, and Saeed Mahloujifar. Bounding training data reconstruction in dp-sgd. Advances in Neural Information Processing Systems, 36, 2023.
[20] Briland Hitaj, Giuseppe Ateniese, and Fernando Perez-Cruz. Deep models under the gan: information leakage from collaborative deep learning. In CCS, 2017.
[21] IBM Federated Learning. https://www.ibm.com/docs/en/cloud-paks/cp-data/4.0?topic=models-federated-learning, April 2022.
[22] Jinwoo Jeon, Jaechang Kim, Kangwook Lee, Sewoong Oh, and Jungseul Ok. Gradient inversion with generative image prior. NeurIPS, 2021.
[23] Georgios A Kaissis, Marcus R Makowski, Daniel Rückert, and Rickmer F Braren. Secure, privacy-preserving and federated machine learning in medical imaging. Nature Machine Intelligence, 2(6):305–311, 2020.
[24] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[25] Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mnist/, 1998.
[26] Hongkyu Lee, Jeehyeong Kim, Seyoung Ahn, Rasheed Hussain, Sunghyun Cho, and Junggab Son. Digestive neural networks: A novel defense strategy against inference attacks in federated learning. computers & security, 2021.
[27] Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50–60, 2020.
[28] Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. In ICLR, 2020.
[29] Yuelong Li, Mohammad Tofighi, Vishal Monga, and Yonina C Eldar. An algorithm unrolling approach to deep image deblurring. In ICASSP, 2019.
[30] Zhuohang Li, Jiaxin Zhang, Luyang Liu, and Jian Liu. Auditing privacy defenses in federated learning via generative gradient leakage. In CVPR, 2022.
[31] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficient learning of deep networks from decentralized data. In AISTATS, 2017.
[32] Microsoft Federated Learning. https://www.microsoft.com/en-us/research/blog/flute-a-scalable-federated-learning -simulation-platform/, May 2022.
[33] RV Mises and Hilda Pollaczek-Geiringer. Praktische verfahren der gleichungsauflösung. ZAMM-Journal of Applied Mathematics and Mechanics/Zeitschrift für Angewandte Mathematik und Mechanik, 9(1):58–77, 1929.
[34] Vishal Monga, Yuelong Li, and Yonina C Eldar. Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing. IEEE Signal Processing Magazine, 38(2):18–44, 2021.
[35] Sayedeh Leila Noorbakhsh, Binghui Zhang, Yuan Hong, and Binghui Wang. Inf2guard: An information-theoretic framework for learning privacy-preserving representations against inference attacks. In USENIX Security, 2024.
[36] Papailiopoulos. https://papail.io/teaching/901/scribe_05.pdf, 2018.
[37] Mert Pilanci and Tolga Ergen. Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks. In ICML, 2020.
[38] Nicola Rieke, Jonny Hancox, Wenqi Li, Fausto Milletari, and et al. The future of digital health with federated learning. NPJ digital medicine, 2020.
[39] Anit Kumar Sahu, Tian Li, Maziar Sanjabi, Manzil Zaheer, Ameet Talwalkar, and Virginia Smith. Federated optimization for heterogeneous networks. arXiv, 2018.
[40] Liwei Song and Prateek Mittal. Systematic evaluation of privacy risks of machine learning models. In USENIX Security, 2021.
[41] Sebastian U Stich. Local SGD converges fast and communicates little. arXiv, 2018.
[42] Sebastian U Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified SGD with memory. In NIPS, pages 4447–4458, 2018.
[43] Jingwei Sun, Ang Li, Binghui Wang, Huanrui Yang, Hai Li, and Yiran Chen. Provable defense against privacy leakage in federated learning from representation perspective. In CVPR, 2021.
[44] Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deep neural networks: analysis and efficient estimation. NeurIPS, 31, 2018.
[45] Zhibo Wang, Mengkai Song, Zhifei Zhang, Yang Song, Qian Wang, and Hairong Qi. Beyond inferring class representatives: User-level privacy leakage from federated learning. In INFOCOM, 2019.
[46] Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H Yang, Farhad Farokhi, Shi Jin, Tony QS Quek, and H Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. IEEE TIFS, 2020.
[47] Wenqi Wei, Ling Liu, Margaret Loper, Ka-Ho Chow, Mehmet Emre Gursoy, Stacey Truex, and Yanzhao Wu. A framework for evaluating client privacy leakages in federated learning. In European Symposium on Research in Computer Security, pages 545–566. Springer, 2020.
[48] Yuxin Wen, Jonas A Geiping, Liam Fowl, Micah Goldblum, and Tom Goldstein. Fishing for user data in large-batch federated learning via gradient magnification. In ICML, 2022.
[49] Ruihan Wu, Xiangyu Chen, Chuan Guo, and Kilian Q Weinberger. Learning to invert: Simple adaptive attacks for gradient inversion in federated learning. In UAI, 2023.
[50] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07747, 2017.
[51] Shangyu Xie and Yuan Hong. Reconstruction attack on instance encoding for language understanding. In EMNLP, pages 2038–2044, 2021.
[52] Shangyu Xie and Yuan Hong. Naacl-hlt. 2022.
[53] Hongxu Yin, Arun Mallya, Arash Vahdat, Jose M Alvarez, Jan Kautz, and Pavlo Molchanov. See through gradients: Image batch recovery via gradinversion. In CVPR, 2021.
[54] Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. In AAAI, 2019.
[55] Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. idlg: Improved deep leakage from gradients. arXiv, 2020.
[56] Junyi Zhu and Matthew Blaschko. R-gap: Recursive gradient attack on privacy. ICLR, 2021.
[57] Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. In NeurIPS, 2019.

1 Input: Model parameters

{\bf w}_{t}

; true gradient

g({\bf x},y)

;

\eta,\lambda

; public generator

G(\cdot)

, transformation operator

\mathcal{T}

2Output: Reconstructed data

\hat{\bf x}

1: if DLG then

{\bf x}_{0}^{\prime}\sim\mathcal{N}(0,1)

y_{0}^{\prime}\sim\mathcal{N}(0,1)

// Initialize dummy inputs and labels.

3: else

4: if GGL then

{\bf z}_{0}^{\prime}\sim\mathcal{N}(0,{\bf I}_{u})

;

6: else

37:

{\bf x}_{0}^{\prime}\sim\mathcal{N}(0,1)

// Initialize dummy input(s)

8: end if

9: Estimate

y

\hat{y}

via methods in [55] for a single input or [53] for a batch inputs

410: end if

511: for

i=0;i<I;i++

12: if DLG then

613:

g({\bf x}_{i}^{\prime},y_{i}^{\prime})\leftarrow\nabla_{\bf w}\mathcal{L}({\bf w}_{t};({\bf x}_{i}^{\prime},y_{i}^{\prime}))

14:

\textrm{GML}_{i}\leftarrow\|g({\bf x},y)-g({\bf x}_{i}^{\prime},y_{i}^{\prime})\|_{2}^{2}

715:

{\bf x}_{i+1}^{\prime}\leftarrow{\bf x}_{i}^{\prime}-\eta\nabla_{{\bf x}_{i}^{\prime}}\textrm{GML}_{i}

y_{i+1}^{\prime}\leftarrow y_{i}^{\prime}-\eta\nabla_{y_{i}^{\prime}}\textrm{GML}_{i}

16: else if iDLG then

17:

g({\bf x}_{i}^{\prime},\hat{y})\leftarrow\nabla_{\bf w}\mathcal{L}({\bf w}_{t};({\bf x}_{i}^{\prime},\hat{y}))

18:

\textrm{GML}_{i}\leftarrow\|g({\bf x},y)-g({\bf x}_{i}^{\prime},\hat{y})\|_{2}^{2}

919:

{\bf x}_{i+1}^{\prime}\leftarrow{\bf x}_{i}^{\prime}-\eta\nabla_{{\bf x}_{i}^{\prime}}\textrm{GML}_{i}

20: else if InvGrad then

1021:

g({\bf x}_{i}^{\prime},\hat{y})\leftarrow\nabla_{\bf w}\mathcal{L}({\bf w}_{t};({\bf x}_{i}^{\prime},\hat{y}))

1122:

\textrm{GML}_{i}\leftarrow 1-\frac{\langle g({\bf x},y),g({\bf x}_{i}^{\prime},\hat{y})\rangle}{\|g({\bf x},y)\|_{2}\cdot\|g({\bf x}_{i}^{\prime},\hat{y}\|_{2}}

1223:

{\bf x}_{i+1}^{\prime}\leftarrow{\bf x}_{i}^{\prime}-\eta\nabla_{{\bf x}_{i}^{\prime}}\big{(}\textrm{GML}_{i}+\lambda\textrm{Reg}_{\textrm{TV}}({\bf x}_{i}^{\prime})\big{)}

24: else if GGL then

1325:

{\bf x}_{i}^{\prime}=G({\bf z}_{i}^{\prime})

1426:

g({\bf x}_{i}^{\prime},\hat{y})\leftarrow\nabla_{\bf w}\mathcal{L}({\bf w}_{t};({\bf x}_{i}^{\prime},\hat{y}))

1527:

\textrm{GML}_{i}\leftarrow\|g({\bf x},y)-\mathcal{T}(g({\bf x}_{i}^{\prime},\hat{y}))\|_{2}^{2}

1628:

\textrm{Reg}(G,{\bf z}_{i}^{\prime})=(\|{\bf z}_{i}\|_{2}^{2}-k)^{2}

1729:

{\bf z}_{i+1}^{\prime}\leftarrow{\bf z}_{i}^{\prime}-\eta\nabla_{{\bf z}_{i}^{\prime}}\big{(}\textrm{GML}_{i}+\lambda\textrm{Reg}(G,{\bf z}_{i}^{\prime})\big{)}

1830: end if

31:

{\bf x}_{i+1}^{\prime}=\max({{\bf x}_{i+1}^{\prime},0})

1932: end for

Return

{\bf x}_{I}^{\prime}

G({\bf z}_{I}^{\prime})

Algorithm 4 Optimization-based DRAs (e.g., DLG, iDLG, InvGrad, and GGL)

Appendix A Assumptions

Assumptions on the devices’ loss function: To ensure FedAvg guarantees to converge to the global optimal, existing works have the following assumptions on the local devices’ loss functions $\{\mathcal{L}_{k}\}$ .

Assumption 1.

$\{\mathcal{L}_{k}\}^{\prime}s$ are $L$ -smooth: $\mathcal{L}_{k}({\bf v})\leq\mathcal{L}_{k}({\bf w})+({\bf v}-{\bf w})^{T}\nabla\mathcal{L}_{k}({\bf w})+\frac{L}{2}\|{\bf v}-{\bf w}\|_{2}^{2},\forall{\bf v},{\bf w}$ .

Assumption 2.

$\{\mathcal{L}_{k}\}^{\prime}s$ are $\mu$ -strongly convex: $\mathcal{L}_{k}({\bf v})\geq\mathcal{L}_{k}({\bf w})+({\bf v}-{\bf w})^{T}\nabla\mathcal{L}_{k}({\bf w})+\frac{\mu}{2}\|{\bf v}-{\bf w}\|_{2}^{2},\forall{\bf v},{\bf w}$ .

Assumption 3.

Let $\xi_{t}^{k}$ be sampled from $k$ -th device’s data uniformly at random. The variance of stochastic gradients in each device is bounded: ${\mathbb{E}}\left\|\nabla\mathcal{L}_{k}({\bf w}_{t}^{k},\xi_{t}^{k})-\nabla\mathcal{L}_{k}({\bf w}_{t}^{k})\right\|^{2}\leq\sigma_{k}^{2},\,\forall k$ .

Assumption 4.

The expected squared norm of stochastic gradients is uniformly bounded, i.e., ${\mathbb{E}}\left\|\nabla\mathcal{L}_{k}({\bf w}_{t}^{k},\xi_{t}^{k})\right\|^{2}\leq G^{2},\forall k,t$ .

Note that Assumptions 1 and 2 are generic. Typical examples include regularized linear regression, logistic regression, softmax classifier, and recent convex 2-layer ReLU networks [37]. For instance, the original FL [31] uses a 2-layer ReLU networks. Assumptions 3 and 4 are used by the existing works [41, 42, 54, 28] to derive the convergence condition of FedAvg to reach the global optimal. Note that the loss of deep neural networks is often non-convex, i.e., do not satisfy Assumption 2. We acknowledge it is important future work to generalize our theoretical results to more challenging non-convex losses.

Appendix B Proof of Theorem 1 for Full Device Participation

Our proof is mainly inspired by the proofs in [41, 54, 28].

Notations: Let $N$ be the total number of user devices and $K(\leq N)$ be the maximal number of devices that participate in every communication round. Let $T$ be the total number of every device’s SGDs, and $E$ be the number of each device’s local updates between two communication rounds. Thus ${T}/{E}$ is the number of communications, assuming $E$ is dividable by $T$ .

Let ${\bf w}_{t}^{k}$ be the model parameter maintained in the $k$ -th device at the $t$ -th step. Let ${\mathcal{I}}_{E}$ be the set of global aggregation steps, i.e., ${\mathcal{I}}_{E}=\{nE\ |\ n=1,2,\cdots\}$ . If $t+1\in{\mathcal{I}}_{E}$ , i.e., the devices communicate with the server and the server performs the FedAvg aggregation on device models. Then the update of FedAvg with partial devices active can be described as

	$\displaystyle\mathbf{v}_{t+1}^{k}={\bf w}_{t}^{k}-\eta_{t}\nabla\mathcal{L}_{k}({\bf w}_{t}^{k},\xi_{t}^{k}),$		(7)
	$\displaystyle{\bf w}_{t+1}^{k}=\left\{\begin{array}[]{ll}\mathbf{v}_{t+1}^{k}&\text{ if }t+1\notin{\mathcal{I}}_{E},\\ \sum_{k=1}^{N}p_{u}\mathbf{v}_{t+1}^{k}&\text{ if }t+1\in{\mathcal{I}}_{E}.\end{array}\right.$		(10)

Motivated by [41, 28], we define two virtual sequences $\mathbf{v}_{t}=\sum_{k=1}^{N}p_{k}\mathbf{v}_{t}^{k}$ and ${\bf w}_{t}=\sum_{k=1}^{N}p_{k}{\bf w}_{t}^{k}$ . $\mathbf{v}_{t+1}$ results from an single step of SGD from ${\bf w}_{t}$ . When $t+1\notin{\mathcal{I}}_{E}$ , both are inaccessible. When $t+1\in{\mathcal{I}}_{E}$ , we can only fetch ${\bf w}_{t+1}$ . For convenience, we define $\overline{{\bf g}}_{t}=\sum_{k=1}^{N}p_{k}\nabla\mathcal{L}_{k}({\bf w}_{t}^{k})$ and ${\bf g}_{t}=\sum_{k=1}^{N}p_{k}\nabla\mathcal{L}_{k}({\bf w}_{t}^{k},\xi_{t}^{k})$ . Hence, ${\mathbf{v}}_{t+1}={{\bf w}}_{t}-\eta_{t}{\bf g}_{t}$ and ${\mathbb{E}}{\bf g}_{t}=\overline{{\bf g}}_{t}$ .

Before proving Theorem 1, we need below key lemmas that are from [41, 28].

Lemma 2 (Results of one step SGD).

Assume Assumptions 1 and 2 hold. If $\eta_{t}\leq\frac{1}{4L}$ , we have

{\mathbb{E}}\left\|{\mathbf{v}}_{t+1}-{\bf w}^{\star}\right\|^{2}\leq(1-\eta_{t}\mu){\mathbb{E}}\left\|{{\bf w}}_{t}-{\bf w}^{\star}\right\|^{2}+\eta_{t}^{2}{\mathbb{E}}\left\|\mathbf{g}_{t}-\overline{\mathbf{g}}_{t}\right\|^{2}+6L\eta_{t}^{2}\Gamma+2{\mathbb{E}}\sum_{k=1}^{N}p_{k}\left\|{{\bf w}}_{t}-{\bf w}_{k}^{t}\right\|^{2}

where $\Gamma=\mathcal{L}^{*}-\sum_{k=1}^{N}p_{k}\mathcal{L}_{k}^{\star}\geq 0$ .

Proof sketch: Lemma 2 is mainly from Lemma 1 in [28]. The proof idea is to bound three terms, i.e., the inner product $\langle{\bf w}_{t}-{\bf w}^{*},\nabla\mathcal{L}({\bf w}_{t})\rangle$ , the square norm $||\nabla\mathcal{L}({\bf w}_{t})||^{2}$ , and the inner product $\langle\nabla\mathcal{L}_{k}({\bf w}_{t}),{\bf w}_{t}^{k}-{\bf w}_{t}\rangle,\forall k$ . Then, the left-hand term in Lemma 2 can be rewritten in terms of the three terms and be bounded by the right-hand four terms in Lemma 2. Specifically, 1) It first bounds $\langle{\bf w}_{t}-{\bf w}^{*},\nabla\mathcal{L}({\bf w}_{t})\rangle)$ using the strong convexity of the loss function (Assumption 2); 2) It bounds $||\nabla\mathcal{L}({\bf w}_{t})||^{2}$ using the smoothness of the loss function (Assumption 1); and 3) It bounds $\langle\nabla\mathcal{L}_{k}({\bf w}_{t}),{\bf w}_{t}^{k}-{\bf w}_{t}\rangle,\forall k$ using the convexity of the loss function (Assumption 2).

Lemma 3 (Bounding the variance).

Assume Assump. 3 holds. Then ${\mathbb{E}}\left\|\mathbf{g}_{t}-\overline{\mathbf{g}}_{t}\right\|^{2}\leq\sum_{k=1}^{N}p_{u}^{2}\sigma_{u}^{2}$ .

Lemma 4 (Bounding the divergence of $\{{\bf w}_{t}^{k}\}$ ).

Assume Assump. 4 holds, and $\eta_{t}$ is non-increasing and $\eta_{t}\leq 2\eta_{t+E}$ for all $t$ . It follows that ${\mathbb{E}}\left[\sum_{k=1}^{N}p_{k}\left\|{{\bf w}}_{t}-{\bf w}_{k}^{t}\right\|^{2}\right]\>\leq\>4\eta_{t}^{2}(E-1)^{2}G^{2}.$

Now, we complete the proof of Theorem 1.

Proof.

First, we observe that no matter whether $t+1\in{\mathcal{I}}_{E}$ or $t+1\notin{\mathcal{I}}_{E}$ in Equation (10), we have ${\bf w}_{t+1}=\mathbf{v}_{t+1}$ . Denote $\Delta_{t}={\mathbb{E}}\left\|{\bf w}_{t}-{\bf w}^{\star}\right\|^{2}$ . From Lemmas 2 to 4, we have

\Delta_{t+1}={\mathbb{E}}\left\|{\bf w}_{t+1}-{\bf w}^{\star}\right\|^{2}={\mathbb{E}}\left\|\mathbf{v}_{t+1}-{\bf w}^{\star}\right\|^{2}\leq(1-\eta_{t}\mu)\Delta_{t}+\eta_{t}^{2}B

(11)

where $B=\sum_{k=1}^{N}p_{u}^{2}\sigma_{u}^{2}+6L\Gamma+8(E-1)^{2}G^{2}.$

For a diminishing stepsize, $\eta_{t}=\frac{\beta}{t+\gamma}$ for some $\beta>\frac{1}{\mu}$ and $\gamma>0$ such that $\eta_{1}\leq\min\{\frac{1}{\mu},\frac{1}{4L}\}=\frac{1}{4L}$ and $\eta_{t}\leq 2\eta_{t+E}$ . We will prove $\Delta_{t}\leq\frac{v}{\gamma+t}$ where $v=\max\left\{\frac{\beta^{2}B}{\beta\mu-1},(\gamma+1)\Delta_{1}\right\}$ .

We prove it by induction. Firstly, the definition of $v$ ensures that it holds for $t=1$ . Assume the conclusion holds for some $t$ , it follows that

	$\displaystyle\Delta_{t+1}$	$\displaystyle\leq(1-\eta_{t}\mu)\Delta_{t}+\eta_{t}^{2}B$
		$\displaystyle\leq\left(1-\frac{\beta\mu}{t+\gamma}\right)\frac{v}{t+\gamma}+\frac{\beta^{2}B}{(t+\gamma)^{2}}=\frac{t+\gamma-1}{(t+\gamma)^{2}}v+\left[\frac{\beta^{2}B}{(t+\gamma)^{2}}-\frac{\beta\mu-1}{(t+\gamma)^{2}}v\right]$
		$\displaystyle\leq\frac{v}{t+\gamma+1}.$

By the $\bar{L}$ -Lipschitz continuous property of $\textrm{Rec}(\cdot)$ ,

\|\textrm{Rec}({\bf w}_{t})-\textrm{Rec}({\bf w}^{*})\|\leq\bar{{L}}\cdot\left\|{\bf w}_{t}-{\bf w}^{\star}\right\|.

Then we have

{\mathbb{E}}\|\textrm{Rec}({\bf w}_{t})-\textrm{Rec}({\bf w}^{*})\|^{2}\leq\bar{{L}}^{2}\cdot{\mathbb{E}}\left\|{\bf w}_{t}-{\bf w}^{\star}\right\|^{2}\leq\bar{{L}}^{2}\Delta_{t}\leq\bar{{L}}^{2}\frac{v}{\gamma+t}.

Specifically, if we choose $\beta=\frac{2}{\mu},\gamma=\max\{8\frac{L}{\mu},E\}-1$ , then $\eta_{t}=\frac{2}{\mu}\frac{1}{\gamma+t}$ . We also verify that the choice of $\eta_{t}$ satisfies $\eta_{t}\leq 2\eta_{t+E}$ for $t\geq 1$ . Then, we have

v=\max\left\{\frac{\beta^{2}B}{\beta\mu-1},(\gamma+1)\Delta_{1}\right\}\leq\frac{\beta^{2}B}{\beta\mu-1}+(\gamma+1)\Delta_{1}\leq\frac{4B}{\mu^{2}}+(\gamma+1)\Delta_{1}.

Hence,

{\mathbb{E}}\|\textrm{Rec}({\bf w}_{t})-\textrm{Rec}({\bf w}^{*})\|^{2}\leq\bar{{L}}^{2}\frac{v}{\gamma+t}\leq\frac{\bar{L}^{2}}{\gamma+t}\Big{(}\frac{4B}{\mu^{2}}+(\gamma+1)\Delta_{1}\Big{)}.

∎

Appendix C Proofs of Theorem 2 for Partial Device Participation

Recall that ${\bf w}_{t}^{k}$ is $k$ -th device’s model at the $t$ -th step, ${\mathcal{I}}_{E}=\{nE\ |\ n=1,2,\cdots\}$ is the set of global aggregation steps; $\overline{{\bf g}}_{t}=\sum_{k=1}^{N}p_{k}\nabla\mathcal{L}_{k}({\bf w}_{t}^{k})$ and ${\bf g}_{t}=\sum_{k=1}^{N}p_{k}\mathcal{L}_{k}({\bf w}_{t}^{k},\xi_{t}^{k})$ , and ${\mathbf{v}}_{t+1}={{\bf w}}_{t}-\eta_{t}{\bf g}_{t}$ and ${\mathbb{E}}{\bf g}_{t}=\overline{{\bf g}}_{t}$ . We denote by ${\mathcal{H}}_{t}$ the multiset selected which allows any element to appear more than once. Note that ${\mathcal{H}}_{t}$ is only well defined for $t\in{\mathcal{I}}_{E}$ . For convenience, we denote by ${\mathcal{S}}_{t}={\mathcal{H}}_{N(t,E)}$ the most recent set of chosen devices where $N(t,E)=\max\{n|n\leq t,n\in{\mathcal{I}}_{E}\}$ .

In partial device participation, FedAvg first samples a random multiset ${\mathcal{S}}_{t}$ of devices and then only performs updates on them. Directly analyzing on the ${\mathcal{S}}_{t}$ is complicated. Motivated by [28], we can use a thought trick to circumvent this difficulty. Specifically, we assume that FedAvg always activates all devices at the beginning of each round and uses the models maintained in only a few sampled devices to produce the next-round model. It is clear that this updating scheme is equivalent to that in the partial device participation. Then the update of FedAvg with partial devices activated can be described as:

	$\displaystyle\mathbf{v}_{t+1}^{k}={\bf w}_{t}^{k}-\eta_{t}\nabla\mathcal{L}_{k}({\bf w}_{t}^{k},\xi_{t}^{k}),$		(12)
	$\displaystyle{\bf w}_{t+1}^{k}=\left\{\begin{array}[]{ll}\mathbf{v}_{t+1}^{k}&\text{ if }t+1\notin{\mathcal{I}}_{E},\\ \text{samples}\ {\mathcal{S}}_{t+1}\text{ and average }\{\mathbf{v}_{t+1}^{k}\}_{k\in{\mathcal{S}}_{t+1}}&\text{ if }t+1\in{\mathcal{I}}_{E}.\end{array}\right.$		(15)

Note that in this case, there are two sources of randomness: stochastic gradient and random sampling of devices. The analysis for Theorem 1 in Appendix B only involves the former. To distinguish with it, we use an extra notation ${\mathbb{E}}_{{\mathcal{S}}_{t}}(\cdot)$ to consider the latter randomness.

First, based on [28], we have the following two lemmas on unbiasedness and bounded variance. Lemma 5 shows the scheme is unbiased, while Lemma 6 shows the expected difference between $\mathbf{v}_{t+1}$ and ${\bf w}_{t+1}$ is bounded.

Lemma 5 (Unbiased sampling scheme).

If $t+1\in{\mathcal{I}}_{E}$ , we have ${\mathbb{E}}_{{\mathcal{S}}_{t}}({\bf w}_{t+1})=\mathbf{v}_{t+1}.$

Lemma 6 (Bounding the variance of ${\bf w}_{t}$ ).

For $t+1\in{\mathcal{I}}$ , assume that $\eta_{t}$ is non-increasing and $\eta_{t}\leq 2\eta_{t+E}$ for all $t\geq 0$ . Then the expected difference between $\mathbf{v}_{t+1}$ and ${\bf w}_{t+1}$ is bounded by ${\mathbb{E}}_{{\mathcal{S}}_{t}}\left\|\mathbf{v}_{t+1}-{\bf w}_{t+1}\right\|^{2}\leq\frac{4}{K}\eta_{t}^{2}E^{2}G^{2}.$

Now, we complete the proof of Theorem 2.

Proof.

Note that

	$\displaystyle\left\\|{\bf w}_{t+1}-{\bf w}^{*}\right\\|^{2}$	$\displaystyle=\left\\|{\bf w}_{t+1}-\mathbf{v}_{t+1}+\mathbf{v}_{t+1}-{\bf w}^{*}\right\\|^{2}$
		$\displaystyle=\underbrace{\left\\|{\bf w}_{t+1}-\mathbf{v}_{t+1}\right\\|^{2}}_{A_{1}}+\underbrace{\left\\|\mathbf{v}_{t+1}-{\bf w}^{}\right\\|^{2}}_{A_{2}}\underbrace{2\langle{\bf w}_{t+1}-\mathbf{v}_{t+1},\mathbf{v}_{t+1}-{\bf w}^{}\rangle}_{A_{3}}.$

When expectation is taken over ${\mathcal{S}}_{t+1}$ , the term $A_{3}$ vanishes due to the unbiasedness of ${\bf w}_{t+1}$ .

If $t+1\notin{\mathcal{I}}_{E}$ , $A_{1}$ vanishes since ${\bf w}_{t+1}=\mathbf{v}_{t+1}$ . We use Lemma 6 to bound $A_{2}$ . Then,

{\mathbb{E}}\left\|{\bf w}_{t+1}-{\bf w}^{*}\right\|^{2}\leq(1-\eta_{t}\mu){\mathbb{E}}\left\|{\bf w}_{t}-{\bf w}^{\star}\right\|^{2}+\eta_{t}^{2}B.

If $t+1\in{\mathcal{I}}_{E}$ , we additionally use Lemma 6 to bound $A_{1}$ . Then,

$\displaystyle{\mathbb{E}}\left\\|{\bf w}_{t+1}-{\bf w}^{*}\right\\|^{2}$	$\displaystyle={\mathbb{E}}\left\\|{\bf w}_{t+1}-\mathbf{v}_{t+1}\right\\|^{2}+{\mathbb{E}}\left\\|\mathbf{v}_{t+1}-{\bf w}^{*}\right\\|^{2}$
	$\displaystyle\leq(1-\eta_{t}\mu){\mathbb{E}}\left\\|{\bf w}_{t}-{\bf w}^{\star}\right\\|^{2}+\eta_{t}^{2}B+\frac{4}{K}\eta_{t}^{2}E^{2}G^{2}$
	$\displaystyle=(1-\eta_{t}\mu){\mathbb{E}}\left\\|{\bf w}_{t}-{\bf w}^{\star}\right\\|^{2}+\eta_{t}^{2}(B+C),$	(16)

where $C=\frac{4}{K}E^{2}G^{2}$ is the upper bound of $\frac{1}{\eta_{t}^{2}}{\mathbb{E}}_{{\mathcal{S}}_{t}}\left\|\mathbf{v}_{t+1}-{\bf w}_{t+1}\right\|^{2}$ .

We observe that the only difference between eqn. (C) and eqn. (11) is the additional $C$ . Thus we can use the same argument there to prove the theorems here. Specifically, for a diminishing stepsize, $\eta_{t}=\frac{\beta}{t+\gamma}$ for some $\beta>\frac{1}{\mu}$ and $\gamma>0$ such that $\eta_{1}\leq\min\{\frac{1}{\mu},\frac{1}{4L}\}=\frac{1}{4L}$ and $\eta_{t}\leq 2\eta_{t+E}$ , we can prove ${\mathbb{E}}\left\|{\bf w}_{t+1}-{\bf w}^{*}\right\|^{2}\leq\frac{v}{\gamma+t}$ where $v=\max\left\{\frac{\beta^{2}(B+C)}{\beta\mu-1},(\gamma+1)\|{\bf w}_{1}-{\bf w}^{*}\|^{2}\right\}$ .

Then by the $\bar{L}$ -Lipschitz continuous property of $\textrm{Rec}(\cdot)$ ,

{\mathbb{E}}\|\textrm{Rec}({\bf w}_{t})-\textrm{Rec}({\bf w}^{*})\|^{2}\leq\bar{{L}}^{2}\cdot{\mathbb{E}}\left\|{\bf w}_{t}-{\bf w}^{\star}\right\|^{2}\leq\bar{{L}}^{2}\Delta_{t}\leq\bar{{L}}^{2}\frac{v}{\gamma+t}.

Specifically, if we choose $\beta=\frac{2}{\mu},\gamma=\max\{8\frac{L}{\mu},E\}-1$ ,

{\mathbb{E}}\|\textrm{Rec}({\bf w}_{t})-\textrm{Rec}({\bf w}^{*})\|^{2}\leq\bar{{L}}^{2}\frac{v}{\gamma+t}\leq\frac{\bar{L}^{2}}{\gamma+t}\Big{(}\frac{4(B+C)}{\mu^{2}}+(\gamma+1)\|{\bf w}_{1}-{\bf w}^{*}\|^{2}\Big{)}.

∎

Appendix D More Experimental Setup

D.1 Details about the FL algorithms and unrolled feed-forward network

We first show how to compute $L,\mu,\sigma_{u}$ , and $G$ in Assumptions 1-4 on federated $\ell_{2}$ -regularized logistic regression ( $\ell_{2}$ -LogReg) and federated 2-layer linear convolutional network (2-LinConvNet); Then we show how to compute the Lipschitz $L_{\mathcal{R}}$ on each data reconstruction attack.

Federated $\ell_{2}$ -LogReg: Each device $k$ ’s local objective is $\mathcal{L}_{k}({\bf w})=\frac{1}{\bar{n}}\sum_{j=1}^{\bar{n}}\log(1+\exp(-y_{j}\langle{\bf w},{\bf x}_{j}^{k}\rangle))\\ +{\gamma}\|{\bf w}\|^{2}$ . In our results, we simply set $\gamma=0.1$ for brevity.

•

Compute ${L}$ : first, all $\mathcal{L}_{k}$ ’s are $\frac{1}{4}(\frac{1}{\bar{n}}\sum_{j}\|x_{j}^{k}\|^{2})$ -smooth [36]; then $L=\max_{k\in[N]}\frac{1}{4}(\frac{1}{\bar{n}}\sum_{j}\|{\bf x}_{j}^{k}\|^{2})+2\gamma$ ;
•

Compute $\mu$ : all $\mathcal{L}_{k}$ ’s are $\gamma$ -strongly convex for the $\gamma$ regularized $\ell_{2}$ logistic regression [36] and $\mu=\gamma$ .
•

Compute $\sigma^{k}$ and $G$ : we first traverse all training data $\xi_{t}^{k}$ in the $k$ -th device in any $t$ -th round and then use them to calculate the maximum square norm differences $\left\|\nabla\mathcal{L}_{k}(w_{t}^{k},\xi_{t}^{k})-\nabla\mathcal{L}_{k}(w_{t}^{k})\right\|^{2}$ . Similarly, $G$ can be calculated as the maximum value of the expected square norm $\left\|\nabla\mathcal{L}_{k}(w_{t}^{k},\xi_{t}^{k})\right\|^{2}$ among all devices $\{k\}$ and rounds $\{t\}$ .

Federated 2-LinConvNet [37]. Let a two-layer network $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ with $m$ neurons be: $f({\bf x})=\sum_{j=1}^{m}\phi({\bf x}^{T}{\bf u}_{j})\alpha_{j}$ , where ${\bf u}_{j}\in\mathbb{R}^{d}$ and $\alpha_{j}\in\mathbb{R}$ are the weights for hidden and output layers, and $\phi(\cdot)$ is an activation function. Two-layer convolutional networks with $U$ filters can be described by patch matrices (e.g., images) ${\bf X}_{u},u=1,\cdots,U$ . For flattened activations, we have $f({\bf X}_{1},\cdots{\bf X}_{u})=\sum_{u=1}^{U}\sum_{j=1}^{m}\phi({\bf X}_{u}{\bf u}_{j})\alpha_{j}$ .

We consider the 2-layer linear convolutional networks and its non-convex loss is:

\displaystyle\min_{\{\alpha_{j},{\bf u}_{j}\}_{j=1}^{m}}\mathcal{L}(\{\alpha_{j},{\bf u}_{j}\})=\frac{1}{2}\|\sum_{u=1}^{U}\sum_{j=1}^{m}{\bf X}_{u}{\bf u}_{j}\alpha_{ju}-{\bf y}\|_{2}^{2}.

(17)

[37] show that the above non-convex problem can be transferred to the below convex optimization problem via its duality. and the two problems have the identical optimal values:

\displaystyle\min_{\{{\bf w}_{u}\in\mathbb{R}^{d}\}_{u=1}^{U}}\mathcal{L}(\{{\bf w}_{u}\})=\frac{1}{2}\|\sum_{u=1}^{U}{\bf X}_{u}{\bf w}_{u}-{\bf y}\|_{2}^{2}.

(18)

We run federated learning with convex 2-layer linear convolutional network, where each device trains the local loss $\mathcal{L}_{k}(\{{\bf w}_{u}\}_{u=1}^{U})$ and it can converge to the optimal model ${\bf w}^{*}=\{{\bf w}_{u}^{*}\}$ .

•

Compute ${L}$ : Let $\underline{\bf w}=\{{\bf w}_{u}\}_{u=1}^{U}$ . For each client $k$ , we require its local loss $\mathcal{L}_{k}$ should satisfy $\left\|\bigtriangledown\mathcal{L}_{k}(\underline{\bf w})-\bigtriangledown\mathcal{L}_{k}(\underline{\bf v})\right\|_{2}\leq{L}_{k}\left\|\underline{\bf w}-\underline{\bf v}\right\|_{2}$ for any $\underline{\bf w},\underline{\bf v}$ ; With Equation 18, we have $\left\|\sum_{u=1}^{U}({\bf X}_{u}^{k})^{T}{\bf X}_{u}^{k}(\underline{\bf w}-\underline{\bf v})\right\|_{2}\leq{L}_{k}\left\|\underline{\bf w}-\underline{\bf v}\right\|_{2}$ ; Then we have the smoothness constant ${L}_{k}$ to be the maximum eigenvalue of $\sum_{u=1}^{U}({\bf X}_{u}^{k})^{T}{\bf X}_{u}^{k}$ , which is $\|\sum_{u=1}^{U}({\bf X}_{u}^{k})^{T}{\bf X}_{u}^{k}\|_{2}$ ; Hence, ${L}=\max_{k}\|\sum_{u=1}^{U}({\bf X}_{u}^{k})^{T}{\bf X}_{u}^{k}\|_{2}$ .
•

Compute $\mu$ : Similar as computing ${L}$ , $\mu$ is the minimum eigenvalue of $\sum_{u=1}^{U}({\bf X}_{u}^{k})^{T}{\bf X}_{u}^{k}$ for all $k$ , that is, $\mu=\min_{k}\|\sum_{u=1}^{U}({\bf X}_{u}^{k})^{T}{\bf X}_{u}^{k}\|_{2}$ .
•

Compute $\sigma^{k}$ and $G$ : Similar computation as in $\ell_{2}$ -regularized logistic regression.

Unrolled feed-forward network and its training and performance. In our experiments, we set the number of layers to be 20 in the unrolled feed-forward network for the three datasets. We use 1,000 data samples and their intermediate reconstructions to train the network. To reduce overfitting, we use the greedy layer-wise training strategy. For instance, the average MSE (between the input and output of the unrolled network) of DLG, iDLG, InvGrad, and GGL on MNIST is 1.22, 1.01, 0.76, and 0.04, respectively—indicating that the training performance is promising. After training the unrolled network, we use the AutoLip algorithm to calculate the Lipschitz $L_{\mathcal{R}}$ .

D.2 Details about Data Reconstruction Attacks

GGL [30]: GGL considers the scenario where clients realize the server will infer their private data and they hence perturb their local models before sharing them with the server as a defense. To handle noisy models, GGL solves an optimization problem similar to InvGrad, but uses a pretrained generator as a regularization. The generator is trained on the entire MNIST dataset and can calibrate the reconstructed noisy image to be within the image manifold. Specifically, given a well-trained generator $G(\cdot)$ on public datasets and assume the label $y$ is inferred by iGLD, GGL targets the following optimization problem:

\displaystyle{\bf z}^{*}=\arg\min_{{\bf z}\in\mathbb{R}^{k}}\text{GML}(g({\bf x},y),\mathcal{T}(g(G({\bf z}),y)))+\lambda\text{Reg}(G;{\bf z}),

(19)

where ${\bf z}$ is the latent space of the generative model, $\mathcal{T}$ is a lossy transformation (e.g., compression or sparsification) acting as a defense, and $\text{Reg}(G;{\bf z})$ is a regularization term that penalizes the latent ${\bf z}$ if it deviates from the prior distribution. Once the optimal ${\bf z}^{*}$ is obtained, the image can be reconstructed as $G({\bf z}^{*})$ and should well align the natural image.

In the experiments, we use a public pretrained GAN generator for MNIST, Fashion-MNIST, and CIFAR. We adopt gradient clipping as the defense strategy $\mathcal{T}$ performed by the clients. Specifically, $\mathcal{T}(g,S)=g/\max(1,{\|g\|_{2}/S})$ . Note that since $G(\cdot)$ is trained on the whole image dataset, it produces stable reconstruction during the optimization.

Robbing [11]: Robbing approximately reconstructs the data via solving an equation without any iterative optimization. Assume a batch of data ${\bf x}_{1},{\bf x}_{2},\cdots{\bf x}_{n}$ with unique labels ${\bf y}_{1},{\bf y}_{2},\cdots{\bf y}_{n}$ in the form of one-hot encoding. Let $\oslash$ be element-wise division. Then, Robbing observes that each row $i$ in $\frac{\partial\mathcal{L}_{t}}{\partial y_{t}}$ , i.e., $\frac{\partial\mathcal{L}_{t}}{\partial y_{t}^{i}}$ , actually recovers

{\bf x}_{t}=\frac{\partial\mathcal{L}_{t}}{\partial y_{t}^{i}}{\bf x}_{t}\oslash\frac{\partial\mathcal{L}_{t}}{\partial y_{t}^{i}}.

In other others, Robbing directly maps the model to the reconstructed data. Hence, in our experiment, the unrolled feed-forward neural network reduces to 1-layer ReLU network. We then estimate Lipschitz upper bound on this network.

	$\displaystyle\mathbb{E}\\|\mathbf{x}-\mathcal{R}({\bf w}_{t})\\|^{2}$	$\displaystyle=\mathbb{E}\\|\mathbf{x}-\mathcal{R}({\bf w}^{\star})+\mathcal{R}({\bf w}^{\star})-\mathcal{R}({\bf w}_{t})\\|^{2}$
		$\displaystyle\leq 2\big{(}\mathbb{E}\\|\mathbf{x}-\mathcal{R}({\bf w}^{\star})\\|^{2}+\mathbb{E}\\|\mathcal{R}({\bf w}^{\star})-\mathcal{R}({\bf w}_{t})\\|^{2}\big{)}.$		(4)

$\displaystyle{\mathbb{E}}\left\\|{\bf w}_{t+1}-{\bf w}^{*}\right\\|^{2}$	$\displaystyle={\mathbb{E}}\left\\|{\bf w}_{t+1}-\mathbf{v}_{t+1}\right\\|^{2}+{\mathbb{E}}\left\\|\mathbf{v}_{t+1}-{\bf w}^{*}\right\\|^{2}$
	$\displaystyle\leq(1-\eta_{t}\mu){\mathbb{E}}\left\\|{\bf w}_{t}-{\bf w}^{\star}\right\\|^{2}+\eta_{t}^{2}B+\frac{4}{K}\eta_{t}^{2}E^{2}G^{2}$
	$\displaystyle=(1-\eta_{t}\mu){\mathbb{E}}\left\\|{\bf w}_{t}-{\bf w}^{\star}\right\\|^{2}+\eta_{t}^{2}(B+C),$	(16)

Understanding Data Reconstruction Leakage in Federated Learning from a Theoretical Perspective

Abstract

1 Introduction

2 Related Work

3 Preliminaries and Problem Setup

3.1 Federated Learning (FL)

3.2 Optimization-based DRAs to FL

4 A Theoretical Framework to Understand DRAs to FL

4.1 Bounding the Data Reconstruction Error

Proposition 1.

Theoretical results with full device participation:

Theorem 1.

Theoretical results with partial device participation:

Theorem 2.

4.2 Computing the Lipschitz Constant for Data Reconstruction Functions

Definition 1 (Deep Feed-Forward Network).

Lemma 1.

5 Evaluation

5.1 Experimental Setup

5.2 Experimental Results

5.2.1 Results on single image recovery

5.2.2 Results on batch images recovery

6 Discussion

7 Conclusion

References

Appendix A Assumptions

Assumption 1.

Assumption 2.

Assumption 3.

Assumption 4.

Appendix B Proof of Theorem 1 for Full Device Participation

Lemma 2 (Results of one step SGD).

Lemma 3 (Bounding the variance).

Lemma 4 (Bounding the divergence of {𝐰tk}\{{\bf w}_{t}^{k}\}).

Proof.

Appendix C Proofs of Theorem 2 for Partial Device Participation

Lemma 5 (Unbiased sampling scheme).

Lemma 6 (Bounding the variance of 𝐰t{\bf w}_{t}).

Proof.

Appendix D More Experimental Setup

D.1 Details about the FL algorithms and unrolled feed-forward network

D.2 Details about Data Reconstruction Attacks

Lemma 4 (Bounding the divergence of $\{{\bf w}_{t}^{k}\}$ ).

Lemma 6 (Bounding the variance of ${\bf w}_{t}$ ).