Differentially Private Principal Component Analysis for Vertically Partitioned Data

Question 1. Wang et al. did "Differentially Private Principal Component Analysis Over Horizontally Partitioned Data," but what is your novelty for vertically partitioned data?

Response. Thanks for the question. We would like to first clarify that existing DP solutions for horizontally partitioned data (including the approach by Wang et al. [7]) do not apply to our setting of vertically partitioned data. The key reason, as we have mentioned in the introduction section, is non-linearity. In the horizontal setting, the clients are able to linearly aggregate their locally perturbed results whereas in the vertical setting, different clients must collaborate to compute the target. In the case of PCA, each entry of the covariance matrix is computed as the inner product between two column vectors possessed by different clients. As a result, the perturbation process cannot be done by a single client alone, since otherwise, the client would learn the sensitive outcome, violating differential privacy.

In terms of contribution, we present the first DP algorithm for PCA over vertically partitioned data that simultaneously protects the partitioned data from both the curious server and curious clients, without assuming any trusted third parties. In addition, our algorithm achieves comparable performance as the strong centralized baseline, which is also a first of its kind in the vertical FL literature. Although it is well known that DP algorithms under horizontal FL are able to achieve comparable performance as in the centralized setting, with the help of secure aggregation or secure shuffling, whether the same can be done under vertical FL, however, has not been answered until this work. We provide a positive answer in this work, which, we believe is a notable contribution to the privacy community.

Question 2. Can you elaborate on how the proposed solution can be practically applied?

Response. To apply our solution in practice, there are four steps in general, as outlined in Algorithm 1 on page 7.

First, each client independently discretizes her local data partition. This computation can be done efficiently on the client side since only multiplication and random rounding are involved (see Algorithm 2).

Next, each client independently samples Skellam noises on the local side privately, which is done by taking the difference between two identically distributed independent Poisson random variables. Sampling algorithms for Poisson are implemented in commonly used libraries such as NumPy and SciPy.

The clients then collaboratively compute the sum of the covariance matrix and the sampled local Skellam noises (as in Eq.(7) on page 6) using any secure multiparty computation (MPC) algorithm without affecting the privacy guarantees (e.g., using the classic BGW protocol). The computation of Eq.(7) involves only summation and multiplication, which are considered elementary operations and can be done efficiently in modern MPC algorithms (e.g., SPDZ by Keller et al. [8]).

Finally, the server reconstructs the covariance matrix from the outcome of MPC in the previous step and computes the $k$-dimensional singular subspace from the covariance matrix on her side. The server is free to use any centralized algorithm for the computation without affecting the privacy guarantees since post-processing preserves DP (e.g., using the power iteration method for efficient computation of eigenvectors [9]).

Thanks for the comments. In what follows, we provide a detailed response. Please kindly let us know if you have any further questions.

Weaknesses 1. Although the paper includes experiments on real-world datasets, the number of experiments is relatively small, which could limit the generalizability of the results.

Response. We believe this is a misunderstanding. First of all, we have included an extensive set of experiments, covering different parameter regimes, including both high-dimensional datasets with $n\ll m$ (CiteSeer and Gene), as well as the KDDCUP dataset, which was commonly used for evaluating PCA (e.g., see Chaudhuri et al. [1]), and the recently released ACSIncome dataset [2] that is commonly used for evaluating FL algorithms. In terms of theory, we have also proved that our solution is able to achieve comparable performance as the strong centralized baseline. Both the empirical results and theoretical analysis confirm the performance and generalizability of our solution.

Weaknesses 2. Comparisons with other existing solutions for differentially private principal component analysis for vertically partitioned data are not presented in the paper.

Response. Thanks for raising this concern. As we have mentioned, existing solutions for private PCA for vertically partitioned data that utilize MPC alone do not provide any rigorous DP guarantees (e.g., see [3,4]). Other works, which attempted to achieve DP under vertical FL by letting one of the clients or a third party to inject random DP noises to the sensitive outcome, are not differentially private either, as the party might be curious and infer the sensitive outcome (e.g., see [5,6]). As a result, these baselines are not comparable with ours, which simultaneously preserves two levels of DP, regarding both a curious server and the curious clients in FL, without assuming any trusted third parties. The only baseline that is comparable to ours is the baseline introduced on page 6 (detailed in Algorithm 3 of page 14), whose performance is much worse than our SPCA, as illustrated in both the theoretical analysis and empirical evaluations.

We want to thank the reviewer for their comments.

As the deadline for the rebuttal phase is approaching, we would like to encourage the reviewer to engage in the interactive rebuttal to help improve our paper and clarify misunderstandings.

We would like to thank the reviewer for the thoughtful comments. In what follows, we provide a detailed response. Please kindly let us know if you have any further questions.

Weakness 1. The utility result of Lemma 3 does not show N, which is an important factor in vertical FL. It would be great to show how N influences the results empirically.

Response. This is an insightful question. The utility result of Lemma 3 and the empirical performance of SPCA is indeed independent of $N$, which is exactly why SPCA achieves comparable performance as the strong centralized baseline (think of it as $N=1$). To explain, recall that the core idea of SPCA is to aggregate $N$ independent Skellam noises distributed as $Sk(\mu/N)$ from the client side into $Sk(\mu)$, a larger Skellam noise. Here, the scale of $\mu$, which determines the result utility, is in turn determined by the required server-observed level of DP, which is independent of $N$.

Instead, what $N$ influences is the level of client-observed DP (with the level of server-observed DP fixed), since each client knows her local DP noise out of the overall N contributions. As $N$ increases, the client-observed level of DP becomes stronger since each client’s knowledge about the overall noise becomes smaller. As an illustration, in what follows, we fix the server-observed level of DP to $\epsilon=4$, $\delta=10^-5$ and vary $N$ from {10,20,40,80,160,320,640} for the ACSIncome data with $d=817$.

We report the corresponding levels of client-observed $\epsilon$ with $\delta$ fixed to $10^{-5}$ for $\gamma=2^{12}$.

Note that the change of $\epsilon$ is almost negligible when $N$ reaches $20$. A similar conclusion also applies to other choices of $d$, $\gamma$, as well as different levels of server-observed $\epsilon$. We have revised the draft to incorporate the above discussion.

Weakness 2. It would be meaningful to present the time/communication cost that happened during the MPC, which is dependent on the choice of $\gamma$.

Response. Thanks for the suggestion. $\gamma$ represents the level of quantization granularity, which is reflected as the number of bits (namely, $\log \gamma$) in communication. For example, quantizing a real number from $0$ to $1$ with $\gamma=2^{12}$ results in a $12$-bit vector. In the case of the classic BGW protocol, the communication is $O(\log \gamma)$ for sharing the secrets. The time complexity, on the other hand, is independent of $\gamma$ as the computation for constructing the secret shares (matrix multiplication) and reconstructing the secret (polynomial interpolation) are done on the client side, and the algorithms for these computations are usually dependent on the size of the input, rather than the range of the input. For example, the Newton interpolation on $N$ points ($N$ secret shares of all clients) incurs a time complexity of $O(N^2)$, which is independent of $\gamma$. In general, the time and communication complexity may vary for different MPC protocols and implementations. We have revised the draft to incorporate the above discussion.

Weakness 3. Dataset release in RMGM-OLS [1] would provide another reasonable baseline: unlike the baseline in the paper which adds noise to the data matrix directly, it adds noise after a random projection, which can reasonably reduce the scaling of noise.

Response. Thanks for the reference. Although random projection is an interesting idea, RMGM-OLS by Wu et al. does not apply to our problem. In particular, the utility goal of Wu et al. (see Eq.(1) on page 3 of their paper) considers linear regression, which is a supervised learning problem. Based on linear regression, the clients are able to train the model weights to better predict the label of the data, a key component of RMGM-OLS. On the contrary, we consider PCA, an unsupervised learning problem where there is no target label. As a result, it is not straightforward to apply RMGM-OLS to PCA and compare it with our solution. We have revised the draft to incorporate the above discussion.

We want to thank the reviewer for their comments.

As the deadline for the rebuttal phase is approaching, we would like to encourage the reviewer to engage in the interactive rebuttal to help improve our paper and clarify misunderstandings.

5. Correctness about proofs.

Response. We apologize for the unclear presentation of the proofs. We have revised the proof. In particular, we have included more details to explain that the sensitivity of the covariance matrix of the quantized data is independent of $m$. We also note that since every non-negative integer $u$ is smaller than or equal to $u^2$ (equality holds for $u=0,1$), we have that $||v||_1\leq ||v||_2^2$ for any integer vector $v$. Finally, we have explicitly stated the parameters in the proof for Lemma 2. Please refer to Page 15 of the revised draft for more details.

6. I assume that what you describe in ''Baseline in vertical FL'' corresponds to what is more commonly known as ''Local differential privacy'', i.e., every client adds so much noise that the publication of the data doesn't allow an adversary to reveal any sensitive information ?.

Response. You are correct. The vertical FL baseline is indeed a local DP algorithm. As we have mentioned in the draft, other existing vertical FL approaches either involve a client, the server, or a third party to perform the noise injection step, which is not differentially private considering that these parties can be curious or do not provide any rigorous DP analysis (such as [7]).

References.

[1]. Peter Kairouz, Ziyu Liu, and Thomas Steinke. 2021. The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation. In ICML.

[2]. Naman Agarwal, Peter Kairouz, and Ziyu Liu. 2021. The Skellam Mechanism for Diferentially Private Federated Learning. In NeurIPS.

[3]. Yuncheng Wu, Shaofeng Cai, Xiaokui Xiao, Gang Chen, and Beng Chin Ooi. Privacy preserving vertical federated learning for tree-based models. In PVLDB.

[4]. Clément L. Canonne, Gautam Kamath, and Thomas Steinke. 2020. The Discrete Gaussian for Diferential Privacy. In NeurIPS.

[5]. Luc Devroye. 1986. Non-Uniform Random Variate Generation. Springer. https://doi.org/10.1007/978-1-4613-8643-8

[6]. Philippe Duchon and Romaric Duvignau. 2016. Preserving the Number of Cycles of Length k in a Growing Uniform Permutation. Electron. J. Comb. 23 (2016), P4.22.

[7]. Thilina Ranbaduge and Ming Ding. Differentially private vertical federated learning. CoRR, abs/2211.06782, 2022.

We would like to thank the reviewer for the thoughtful comments. In what follows, we provide a detailed response. Please kindly let us know if you have any further questions.

1. The brute-force baseline.

Response. Indeed, we have considered the brute-force algorithm you mention above, where for each $C(i,j)$, only the corresponding clients who own columns $i$ and $j$ (say client $p$ and client $q$) participate in the secret sharing process. However, this brute-force approach has the drawback that both client $p$ and client $q$ know exactly half the overall DP noise. As a result, it is easier for client $q$ to infer the data of client $p$, compared with our solution, where both client $p$ and $q$ know only $1/N$ of the overall DP noise. In cases when $N>2$, our solution is more private considering curious clients.

2. Client's knowledge of $Sk(\mu/N)$.

Response. You are correct. From a client’s perspective, the DP guarantee is provided by $Sk((N-1)\mu/N)$. Hence, the levels of client-observed DP and server-observed DP (which is provided by $Sk(\mu)$) are different, as we have stated in Lemma 2 (see Eq.(9) and Eq.(10) in page 8). For better comparison with previous works from the centralized setting and the horizontal FL setting [1,2], we focus on server-observed DP. The corresponding levels of client-observed DP are reported in Tables 1 and 2 of page 17.

3. The minimal noise.

Response. You are correct. We could not technically prove that our noise is minimal. We have revised the term minimal noise to ``noise of scale comparable with the strong centralized baseline'' in the draft.

4. Alternative solution for collaborative sampling from $Sk(\mu)$.

Response. Although it is a tempting idea to let the clients sample from $Sk(\mu)$ directly while getting rid of the slackness of $1/N$, we are not aware of any efficient and rigorous approach to do so under distributed FL settings (either vertical or horizontal).

In particular, the slackness of $1/N$ was also observed in the state-of-the-art approaches of horizontal FL [1,2], where each client independently injects locally generated DP noises to the sensitive outcome. Wang et al. [3] attempted to remove the slackness by letting the clients jointly sample from a discrete Gaussian distribution using a shared random seed. However, as pointed out by Kairouz et al. [1], a single curious client could learn the overall DP noise from the shared seed, leading to privacy violation.

In vertical FL, Wu et al. [3] propose to use a secret-shared random seed to generate Laplace noise to achieve DP when generating decision trees under vertical FL. However, they did not provide any formal DP analysis from the perspective of a curious client. In addition, the process for converting shared randomness to the designated distribution of DP noise (e.g., discrete Gaussian [1] and Skellam [2]) might be a huge overhead for the clients to bear, considering that even the centralized algorithms for generating discrete Gaussian and Skellam distributions from random bits are complicated and time-consuming (see Section 5 in [4], page 487 of [5], and [6]) and the clients also need to synchronize repeatedly in such complicated algorithms under the MPC model.

On the contrary, the overhead of DP in SPCA comes from the addition of $N$ Skellam noises, as the client can generate Skellam noises in an offline manner without collaboration. This overhead of $N$ additions is not significant when compared with the computation of an element in the covariance matrix that involves the addition of $m$ multiplications, considering that the number of clients $N$ is usually much smaller than the number of records $m$ in vertical FL. In addition, when $N$ is large, the difference between $N$ and $N-1$ becomes negligible. Further closing this gap would be an interesting direction to explore.

Thanks for your kind explanations.

We agree that the brute-force approach you have suggested indeed is better than our proposed solution in terms of the privacy-utility trade-off from the perspective of a curious client, who no longer has the knowledge of $Sk(\mu/N)$.

However, we would like to point out that, still, the difference may be negligible in scenarios where $N$ is large (e.g., $N=20$). In addition, in certain scenarios, the cost of the brute-force approach could be more significant (despite that it is a constant regarding the size of data). For example, considering the Skellam noise generation with a large $\mu$ (corresponding to strong privacy constraints), the clients would need to collaboratively generate $\mu$ independent copies of $Sk(1)$ (let's say $\mu$ is an integer for the ease of discussion), which could be time-consuming. On the other hand, in our solution, each of the $N$ clients independently generates a much smaller Skellam noise in a more efficient offline manner, which could be an advantage under strong privacy constraints and when the number of records is small.