Noise-Aware Algorithm for Heterogeneous Differentially Private Federated Learning

Thank you for your feedbacks and comments about our work. We are happy to answer your comments and questions:

Comment1: A client with a larger dataset will have larger $E_i$ and thus higher noise.

A1: The equation for $\sigma_i^2$ can be found in eq. 7, 5 and 3, where $N_i$ appears twice with opposite effects. Hence $\sigma_i^2$ varies very slowly with $N_i$ (we have experimentally confirmed this). This means that the noise variance $\sigma_i^2$ of a client is mainly determined by its privacy parameter $\epsilon_i$ and batch size $b_i$. So if two clients have similar $\epsilon_i$ and $b_i$, the aggregation weight assigned to them by Robust-HDP is very close, even if their dataset sizes are different. In contrast, DPFedAvg assigns lower weights to clients with smaller dataset sizes. As all clients have the same $\sigma_i^2$ in this case, it makes sense to assign larger weights to the clients with larger dataset sizes (as DPFedAvg does) to improve utility. But what happens to fairness in the system? it has been shown that accuracy of DP models drops much more for the underrepresented subgroups [1]. Hence, in some scenarios, we expect that Robust-HDP improves fairness in the system for clients with lower $N_i$. For instance, the following results evaluate the utility and also fairness in the system when we have homogeneous DPFL and only $N_i$ varies across clients:

[1]: E. Bagdasaryan, "Differential Privacy Has Disparate Impact on Model Accuracy", arXiv 2019.

• utility (average test accuracy). Note that PFA and WeiAvg are equivalent when $\\{\epsilon_i\\}_i$ is uniform: | Algorithm | $\epsilon=2.6$ | $\epsilon=2$ | $\epsilon=1.1$ | $\epsilon=0.6$ | $\epsilon=0.35$ | |-------------------------------------------|--------------------|-----------------|--------------------|--------------------|--------------------| | WeiAvg and PFA | 37.24 | 34.90 | 27.80 | 23.22 | 19.01 | | DPFedAvg and minimum $\epsilon$ | 38.52 | 32.78 | 30.42 | 23.50 | 20.26 | | Robust-HDP | 37.68. | 32.54. | 27.51 | 22.58 | 20.52 |

• performance fairness, measured by std of clients test accuracies and also the test accuracy of the client with smallest dataset size ($N_i$) (in parentheses): | Algorithm | $\epsilon=2.6$ | $\epsilon=2$ | $\epsilon=1.1$ | $\epsilon=0.6$ | $\epsilon=0.35$ | |-------------------------------------------|----------------------|--------------------|-------------------|------------------------|--------------------| | WeiAvg and PFA | 4.24 (32.95) | 4.11 (30.68) | 4.95 (25.01) | 3.89 (27.84) |5.70 (17.04) | | DPFedAvg and minimum $\epsilon$ | 4.92 (34.69) | 4.71 (29.54) | 4.95 (25.41) | 6.78 (14.77) |6.86 (11.36) | | Robust-HDP | 4.77 (34.09) | 4.59 (34.91) | 4.66 (26.13) | 6.01 (15.34) | 3.89 (18.97) |

We observe that when we have homogeneous $b_i$ and $\epsilon_i$ and heterogeneous $N_i$, using Robust-HDP results in more fairness in the system, as it assigns more balanced weights to clients in this case.

Comment2: The experimental results shown in the body part are mainly on MNIST and FMNIST.

A2: Following your comment and other reviewers, we have added multiple experimental results on CIFAR10 and also with an even larger model ResNet-34 to evaluate Robust-HDP in more complex cases. Experimental results still show the superiority of Robust-HDP. Please read our answer A2 to reviewer fjuK for results in more complex settings.

Please continue to our second official comment in the following:

Comment3: Also, the results of CIFAR10 seem to be lost in the Appendix

A3: By mistake, we did not include the table of detailed results for CIFAR10 in the appendix at the submission time. We have now included it in the following:

Q1: I do not find how the data heterogeneity is simulated in the experiments

A4: In section A.1 of the appendix (DATASETS AND MODELS), we have explained in details how we distribute data across clients. We first split each existing class into some shards. Then, depending on the desired level of data heterogeneity, we decide about the maximum number of classes that each client can have samples from. This results in uniform dataset size across clients. In cases where we want to have quantity shift, we use Dirichlet allocation.

Q2: the server can eliminate the noise from the model and get the noise-free results of the local model update

A5: Based on post-processing property, it's always safe to perform arbitrary computations on the output of a differentially private mechanism, so it is OK to use the matrix $L$ at aggregation time. However, our results show that using $L$ is not better than using $M$ with the aggregation weights coming from Robust-HDP.

Thank you for your feedbacks and comments about our work. We are happy to answer your comments and questions:

Comment1: The result stated in Lemma 1 seems to be independent of the use of RPCA.

A1: Lemma1 says that if RPCA can extract the matrix $S$ up to a factor $r$, then Robust-HDP can estimate the clients noise variances $\\{\sigma_i^2\\}_i$ up to a factor $r^2$. In ideal case $r=1$ and $\alpha_j=0$. Based on the theoretical results in the RPCA paper, as rank of $L$ decreases and the additive noisy matrix $S$ gets more sparse (which we have explained in the following why this is the case), we get closer to the ideal case of extracting $S$ exactly. Therefore, the parameters $r$ and $\alpha_j$ depend on the given matrix $M$ and the RPCA algorithm. On the other hand, for our purpose of estimating the optimum weights $w_i^*$, estimating the elements in $S$ up to a factor $r$ is sufficient (so for our goal, $r$ does not need to be necessarily $1$). As an instance for MNIST and Dist8, we can see from Figure 4 that $\frac{\hat{\sigma}_i^2}{\sigma_i^2} \approx r^2$ is very close to 1 for all the 20 clients in the system. This means that for MNIST that $M$ has columns of dimension $p=28,939$ (number of model parameters), RPCA can estimate $S$ with a good precision, which consequently results in the estimates $\\{\hat{\sigma}_i^2\\}_i$ being very close to their true values $\\{\sigma_i^2\\}_i$.

Now consider the case where $p$ is too large, e.g. for the ResNet18 ($p=11,181,642$) or ResNet34 ($p=21,272,778$). Then running RPCA on the matrix $M$, not only takes long time, but also it might result in lower precision in extracting $S$. Hence, we proposed our approximation approach relying on two facts: 1. in our heterogeneous DPFL problem, all the components in $S_{:,i}$ are iid, because they were sampled and added by the same client $i$ during its local DP training 2. We want to estimate $\sigma_i^2 = ||S_{:,i}||^2= \sum_{l=1}^p Sl,i^2$, which is the sum of the variances of the iid samples $\\{Sl,i\\}_{l=1}^p$. As sample variance decreases inversely proportional to the number of samples, even if we estimate $\sigma_i^2$ by running RPCA on a submatrix of $M$ with $1\ll p' \ll p$ (e.g. $p'=200,000$ that we used), we still get to an approximation of $\sigma_i^2$ up to a factor $\frac{p'}{p}$, which is sufficient for Robust-HDP to get to the optimum weights $\\{w_i^*\\}_i$. Our multiple improved experimental results on CIFAR10 shows that the approximation idea is indeed effective.

Comment2: I can understand that the matrix $M$ can be deposed into a low rank signal component $L$ and a noise component $S$, but why should one believes that $S$ is sparse?

A2: As shown in Figure 1, $\sigma_i^2$, which is equal to $||S_{:,i}||^2$, heavily depends on $\epsilon_i$ and $b_i$. When both $\epsilon_i$ and $b_i$ are small, $\sigma_i^2$ increases fast, and in other cases it has relatively smaller values. The heterogeneity in clients privacy parameters $\epsilon_i$ and batch sizes $b_i$ results in a variation between $\{\sigma_i^2\}$ across clients, which makes the sparse patterns similar to what observed in Figure 4 or Figure 10 (in the appendix) for $\sigma_i^2$. Now note that a few of existing clients might be in the peak corner of Figure 1. Hence, the pattern in $\\{\sigma_i^2=||S_{:,i}||^2\\}$ is sparse. This means that some columns of $S$ have large norm and some others have small norms. Now, note that the elements in $\mathbf{S}_{:,i}$ are iid with mean 0 (they are noise elements), this means that $\mathbf{S}$ is also sparse, or more precisely most columns of $S$ hold elements with small magnitude and some other columns have elements with relatively larger magnitudes. Hence $S$ is can be thought of as being sparse (again see the pattern in Fig. 4 of the norms of the 20 columns of $S$ ).

Comment3:The authors also mention that $\sigma_j^2 \gg 1$.

A3: Based on the definition above, $\sigma_j^2$ is the noise variance in the whole model update of dimension $p$. It can be computed from eq.7, which is computed based on either eq.3 or eq.5. In either case, the terms in equations 3 and 5 are large, mainly because $p$ which is the number of model parameters, has a large value (e.g. 11,181,642 for CIFAR10 or 28,938 for MNIST/FMNIST). Also $c$ (clipping threshold), and $z$ (the DP noise scale) are constants around 1. In order to get an idea of the values of $\sigma_i^2$, see the values in Figure 4 left, which shows the true noise variance existing in each of the 20 clients model updates.

Q1: I believe a definition of Var is needed as I don't see how it maps from a vector to a scalar (e.g.\ in (3) and (5)).

A4: First, for a vector $V$ of dimension $p$ we have: $`Var`(V) = \sum_{I=1}^p \mathbb{E}[(v_i - \mathbb{E}[v_i])^2]$. So it captures the deviations of $V$ from its mean. Note than when $v_i$ are iid and $p$ increases, $`Var`(V)$ also increases.

Thank you for your feedbacks and comments about our work. We are happy to answer your comments and questions:

Q1: Does your approach lead users to lie about ...?

A1: The answer is no. Because our algorithm does not operate based on clients privacy parameters $\{\epsilon_i\}$. Whether the server knows $\\{\epsilon_i\\}_i$ or not does not affect Robust-HDP, because it operates based on estimating the amount of noise in clients model updates $\\{\sigma_i^2\\}_i$. However WeiAvg/PFA do heavily depend on the server knowing clients privacy parameters. Due to this dependence , a client could also lie about their $\epsilon_i$ and mislead the server, which runs WeiAvg/PFA, by pretending that they are a less privacy sensitive client by sending a larger $\epsilon$ .

Q2: Simulations where $\epsilon_i$ and $b_i$ are uniform.

A2: We ran a set of experiments with different assumptions. Unlike before where we assumed heterogeneous $\epsilon_i$, heterogeneous $b_i$ and uniform dataset size $N_i$, we experimented with the following cases. As asked in your comments, all the the experiments are run on CIFAR-10 (instead of MNIST/FMNIST), which uses ResNet18 with $11, 181, 642$ parameters:

case 1. uniform $\{bi = 32\}$, heterogeneous $\epsilon_i$ and heterogeneous $N_i$. Results for homogeneous $b_i=b=32$ and heterogeneous $\epsilon_i$ on CIFAR10, still shows superiority of Robust-HDP:

case 2. heterogeneous $\{bi\}$, uniform $\epsilon_i=\epsilon$ ($\epsilon$ is fixed to mean of distributions 1, 3, 5 and 7), and heterogeneous $N_i$ (quantity shift):

case 3. uniform $\{bi\}$, uniform $\epsilon_i=\epsilon$ and heterogeneous $N_i$: this is the regular homogeneous DPFL, for which DPFedAvg is designed. Based on equations 7, 5 and 3, $\sigma_i^2$ changes across clients just based on their dataset size $N_i$. However, $N_i$ appears twice in eq.7 with different effects. Hence $\sigma_i^2$ varies very slowly with $N_i$ (we have experimentally confirmed this). Therefore, Robust-HDP (which solves problem 8) and WeiAvg ($w_i \propto \epsilon_i$) assign uniform aggregation weights $w_i$ to all clients. However, DPFedAvg assigns larger weights to clients with larger dataset size ($w_i \propto N_i$). As all clients have the same $\sigma_i^2$ in this case, it makes sense to assign larger weights to the clients with larger dataset sizes (as DPFedAvg does) to improve utility. But what happens to fairness in the system? it has been shown that accuracy of DP models drops much more for the underrepresented subgroups [1]. Hence, in some scenarios, we expect that Robust-HDP improves fairness in the system for clients with lower $N_i$. For instance, the following results evaluate the utility and also fairness in the system when we have homogeneous DPFL and only $N_i$ varies across clients. We have looked at std of clients test accuracies and also the test accuracy of the client with smallest dataset size ($N_i$) (in parentheses).

[1]: E. Bagdasaryan, "Differential Privacy Has Disparate Impact on Model Accuracy", arXiv 2019.

Please continue to the our second official comment below:

• utility (average test accuracy). Note that PFA and WeiAvg are equivalent when $\\{\epsilon_i\\}_i$ is uniform: | Algorithm | $\epsilon=2.6$ | $\epsilon=2$ | $\epsilon=1.1$ | $\epsilon=0.6$ | $\epsilon=0.35$ | |-------------------------------------------|--------------------|-----------------|--------------------|--------------------|--------------------| | WeiAvg and PFA | 37.24 | 34.90 | 27.80 | 23.22 | 19.01 | | DPFedAvg and minimum $\epsilon$ | 38.52 | 32.78 | 30.42 | 23.50 | 20.26 | | Robust-HDP | 37.68. | 32.54. | 27.51 | 22.58 | 20.52 |

• performance fairness, measured by std of clients test accuracies and also the test accuracy of the client with smallest dataset size ($N_i$) (in parentheses): | Algorithm | $\epsilon=2.6$ | $\epsilon=2$ | $\epsilon=1.1$ | $\epsilon=0.6$ | $\epsilon=0.35$ | |-------------------------------------------|----------------------|--------------------|-------------------|------------------------|--------------------| | WeiAvg and PFA | 4.24 (32.95) | 4.11 (30.68) | 4.95 (25.01) | 3.89 (27.84) |5.70 (17.04) | | DPFedAvg and minimum $\epsilon$ | 4.92 (34.69) | 4.71 (29.54) | 4.95 (25.41) | 6.78 (14.77) |6.86 (11.36) | | Robust-HDP | 4.77 (34.09) | 4.59 (34.91) | 4.66 (26.13) | 6.01 (15.34) | 3.89 (18.97) |

We observe that when we have homogeneous $b_i$ and $\epsilon_i$ and heterogeneous $N_i$, using Robust-HDP results in more fairness in the system, as it assigns more balanced weights to clients in this case.

• Conclusion: Based on the three experimental cases above, when there is heterogeneity in either $\\{b_i\\}_i$ or $\\{\epsilon_i\\}_i$ (or both), using Robust-HDP is beneficial, because in these cases $\\{\sigma_i^2\\}_i$ is also heterogeneous (according to eqs 7, 5 and 8). However, when both $b_i$ and $\epsilon_i$ are uniform (i.e. regular homogeneous DPFL), then $\sigma_i^2$ is almost fixed across clients and it makes sense to use DPFedAvg to assign larger weights to clients with larger dataset sizes $N_i$ and improve utility.

Q3: Larger Scale models in simulations.

A3: We ran experiments on CIFAR10 with ResNet34 with $p=21,272,778$. Due to lack of time, we could run these experiments only with heterogeneous $b_i$ and heterogeneous $\epsilon_i$ (sampled from Dist3) and $E=100$ rounds:

Thank you for your feedbacks and comments.

Q1: framing the discussion around client memory limitations seems a bit weird.

A1: Even with gradient accumulation, the amount of DP noise in clients updates, depends on the base batch size that they use. The accumulation of $m$ batch gradients with base batch size $b_i$, which is used for model updates is: $\\sum_{j=1}^m \bigg( \frac{1}{b} \bigg [ \big (\sum_{i \in \mathcal{B}_j} \bar{g}_i(\theta) \big) + \mathcal{N}(0, \sigma^2 I_p) \bigg]\bigg),$ where $\sigma = c.z(\epsilon_i, \delta_i, \mathbf{\frac{b_i}{N_i}}, K_i, E)$ depends on the base sampling ratio $\frac{b_i}{N_i}$ that the client uses for computing batch gradients. Therefore, although the stochastic noise in accumulated batch gradient decreases, the total DP noise induced in the model update of each client after $K_i$ local epochs does not change (compared to when we use batch size $b_i$). Hence heterogeneity in the base batch sizes $b_i$ results in heterogeneity in $\sigma_i^2$. This being said, consider when all clients use the same batch size $b_i=b$, but their privacy parameters are heterogeneous. Based our analysis in eq. 7, 5 and 3, this results in the induced noise variances $\sigma_i^2$ being heterogeneous. This makes WeiAvg a suboptimal solution. In contrast Robust-HDP assigns aggregation weights based on the real noise variance in clients model updates ($\{\sigma_i^2\}$), instead of their privacy parameters $\{\epsilon_i\}$ (which might not even be shared with the server). Also, for Robust-HDP does not matter if $\epsilon_i$ are known by server or not, because it does not use them, so it gives clients more "freedom" for not sharing them with the server. Results for homogeneous $b_i=b=32$ and heterogeneous $\epsilon_i$ on CIFAR10, still shows superiority of Robust-HDP:

Q2: How sensitive the rank of M is for client heterogeneity?

A2: We have run some experiments on MNIST and instead of assigning all classes to all (20) clients, we have limited the number of classes per client to be at maximum 8, which results in more data heterogeneity. Note that RPCA needs the matrix $M$ to have "low rank" (not rank 1). So as long as the data heterogeneity across clients results in a low rank $M$, RPCA and consequently Robust-HDP can be used to improve utility, especially when $\epsilon_i$ are small:

Q3: In eq.3: any reasoning about when the final approximation is good?

A3: First, for a vector $V$ of dimension $p$ we have: $`Var`(V) = \sum_{I=1}^p \mathbb{E}[(v_i - \mathbb{E}[v_i])^2]$. From the values that we had in our experiments, the first term in eq.3 is less than 1 (similarly $\frac{c^2}{b_i^2}$ in the second term is smaller than 1 too): because $c$ is set to 3 in our experiments and $b_i$ is a random value from $\\{16, 32, 64, 128\\}$. On the other hand $p$ (the number of model parameters) is large (e.g. 11,181,642 for CIFAR10 or 28,938 for MNIST/FMNIST) which makes the second term much larger than the first term (look at numbers in Figure 4). Hence, the approximation makes complete sense.

Q4: Please mention the neighbourhood relation explicitly in defining DP.

A4: Two datasets $\mathcal{D}_i$ and $\mathcal{D}'_i$ (for client $i$) are adjacent datasets, if they differ in only one data sample (present in one dataset and absent in the other one). Therefore, our notion of adjacency is sample level.

Q5: Fig.2 caption have some broken references.

Please continue to the our second official comment below:

Q5: Fig.2 caption have some broken references.

A5: By mistake, we did not include the table of detailed results for CIFAR10 in the appendix at the submission time. We have now included it in the following:

comment1: It is not clear from the theory or from the provided empirical results how feasible the approximation approach actually is.

A6: Lemma1 says that if RPCA can extract the matrix $S$ up to a factor $r$, then Robust-HDP can estimate the clients noise variances $\\{\sigma_i^2\\}_i$ up to a factor $r^2$. In ideal case $r=1$ and $\alpha_j=0$. Based on the theoretical results in the RPCA paper, as rank of $L$ decreases and the additive noisy matrix $S$ gets more sparse, we get closer to the ideal case of extracting $S$ exactly. Therefore, the parameters $r$ and $\alpha_j$ depend on the given matrix $M$ and the RPCA algorithm. On the other hand, for our purpose of estimating the optimum weights $w_i^*$, estimating the elements in $S$ up to a factor $r$ is sufficient (so for our goal, $r$ does not need to be necessarily $1$). As an instance for MNIST and Dist8, we can see from Figure 4 that $\frac{\hat{\sigma}_i^2}{\sigma_i^2} \approx r^2$ is very close to 1 for all the 20 clients in the system. This means that for MNIST that $M$ has columns of dimension $p=28,939$ (number of model parameters), RPCA can estimate $S$ with a good precision, which consequently results in the estimates $\\{\hat{\sigma}_i^2\\}_i$ being very close to their true values $\\{\sigma_i^2\\}_i$.

Now consider the case where $p$ is too large, e.g. for the ResNet18 ($p=11,181,642$) or ResNet34 ($p=21,272,778$). Then running RPCA on the matrix $M$, not only takes long time, but also it might result in lower precision in extracting $S$. Hence, we proposed our approximation approach relying on two facts: 1. in our heterogeneous DPFL problem, all the components in $S_{:,i}$ are iid, because they were sampled from the same normal distribution and added by the same client $i$ during its local DP training 2. We want to estimate $\sigma_i^2 = ||S_{:,i}||^2= \sum_{l=1}^p Sl,i^2$, which is the sum of the variances of the iid samples $\\{Sl,i\\}_{l=1}^p$. As sample variance decreases inversely proportional to the number of samples, even if we estimate $\sigma_i^2$ by running RPCA on a submatrix of $M$ with $1\ll p' \ll p$ (e.g. $p'=200,000$ that we used), we still get to an approximation of $\sigma_i^2$ up to a factor $\frac{p'}{p}$, which is sufficient for Robust-HDP to get to the optimum weights $\\{w_i^*\\}_i$. Our multiple improved experimental results on CIFAR10 shows that the approximation idea is indeed effective.