Differentially Private Low-dimensional Synthetic Data from High-dimensional Datasets

Weakness

Thank you for pointing out the mistake. Indeed, by Laplacian mechanism, to protect $\overline{X}\in \mathbb{R}^d$ with parameter $\varepsilon$ needs entry-wise noises of $\mathrm{Lap}(\frac{d}{\varepsilon n})$, and hence the private mean estimation would have a slightly worse accuracy bound $O(d/n)$. Together with Weakness 2, we will change the privacy budget of each step in Algorithm 1 to have a correct level of privacy, and we will update the result in the simulation experiments. Nevertheless, it would only influence the final result by $O(d/n)$, and this is an inconsequential term compared with the dominating term $n^{-1/d'}$. Therefore, the final accuracy bound Theorem 4.2 for the main low-dimensional synthetic data algorithm remains to be true.

Questions

(1) We compare the accuracy of SVM when applied on the true and synthetic data separately. Our experiment suggests the low-dimensional synthetic data approach is useful for classification tasks.

The theoretical utility of Wasserstein bound is guaranteed by the Kantorovich-Rubinstein duality, which ensures the accuracy of all the Lipschitz tasks. (See the last equation in Appendix A.) As there are alternative variations of SVM, the practical guarantee is out of the scope for this paper.

(2) Without DP requirement, the accuracy of SVM is around 95%.

The experiment in the paper can be seen as a proof of concept for the Wasserstein accuracy bound we proved. As a result, the low-dimensional algorithm does overcome the curse of high-dimensionality. Optimizing the algorithm more practically could potentially increase SVM's performance. However, it is not the main focus of our work in this paper.

(3) $\sigma_i(M)$ denotes the $i$-th largest singular value of $M$. Here $M$ is semi-positive-definite, so it is also the $i$-th largest eigenvalue.

(4) Thank you for the question. We mentioned the Adaptive and private choices of $d'$ at Section 1.1, but we omit the details of such optimal choice due to space limitation. We will add the details of the choice of $d'$ in Appendix E. The main idea for the choice of $d'$ is to balance different error terms Theorem 4.2; we can choose the best $d'$ to minimize the error. Such a minimization problem would be time-efficient as we only need the values of the singular values of the private covariance matrix.

Weakness

(1) The method of Donhauser et al. (20203) uses the exponential mechanism and it is not very efficient to implement. Our approach is computationally efficient and has a better theoretical guarantee in terms of the error rate. Our main focus is on the theoretical guarantees therefore we do not implement their methods in this work.

(2) We mentioned the Adaptive and private choices of $d'$ at Section 1.1, but we omit the details of such optimal choice due to space limitation. The idea is exactly the gist of Question 2: to choose the best $d'$ privately by balancing different terms in the error bound in Theorem 4.2. (And as mentioned in the question, $\sigma_i(\widehat{\mathbf M})$'s are needed to estimate $d'$ privately.) Moreover, such optimization is time efficient. We will add the details of the choice of $d'$ in Appendix E.

Questions

(1) The result of $(\varepsilon n)^{-1/(d'+1)}$ is from Theorem 3 in Donhauser et al. (2023). In their settings, the test function is also all the 1-Lipschitz functions, and the dataset is in a low-dimensional manifold with Minkowski dimension $d'$.

(2) Thank you for the suggested approach. We mentioned the Adaptive and private choices of $d'$ at Section 1.1, but we omit the details of such optimal choice due to space limitation. The idea is exactly the gist of Question 2: to choose the best $d'$ privately by balancing different terms in the error bound in Theorem 4.2. (And as mentioned in the question, $\sigma_i(\widehat{\mathbf M})$'s are needed to estimate $d'$ privately.) Moreover, such optimization is time efficient. We will add the details of the choice of $d'$ in Appendix E.

Minor

(1) This is the mean value of the original dataset.

(2) Thank you for the suggestion. Saving the private mean and using it afterward would have better accuracy than adding noises twice. We changed the algorithm to have a more reasonable privacy budget distribution. Nevertheless, it will only influence the final accuracy bound by $O(1/n)$, which is dominated by the $n^{-1/d'}$ term.

(3) Thank you for pointing it out. Combining with the suggestion in Minor Question 2, we reassign the privacy budget in Algorithm 1 in the correct way.

(4) In the algorithm, we define the matrix $A$ to be symmetric, so the entries below the diagonal are implied from the other entries. We will make it clearer in the modification.

I thank the authors for addressing all of my questions. I think that the authors have provided sufficient theoretical contribution toward DP synthetic data, but a bit insufficient for practical considerations. I understand that the method from Donhauser et al. (2023) is cumbersome to implement.

In addition to experimenting on downstream tasks, I recommend generating data from a simple model (e.g. well-separated mixture of gaussians) and measure the statistical distance between the model fitted from synthetic data and the original model.

I have raised the score by 1.

Weakness

(1) Yes, there would be a trade-off, and it is possible to choose a better value of $d'$ privately. We mentioned the Adaptive and private choices of $d'$ at Section 1.1, but we omit the details of such optimal choice due to space limitation. We will add the details of the choice of $d'$ in the appendix. The main idea for the choice of $d'$ is to balance different terms in the error bound of Theorem 4.2, and we can choose the best $d'$ to minimize the error. Such a minimization problem would be time-efficient as we only need the values of the singular values of the private covariance matrix.

For a non-trivial bound of Wasserstein distance, we need the number of data $n$ to be exponentially large w.r.t. $d'$. If $d'$ is too large, one can try to reduce $d'$ as long as the original data has a lower-dimensional structure (in the sense of singular values $\sigma_i(M)$'s). In the case when further decreasing $d'$ is not possible, the lower bound in (Boedihardjo et al. 2022) implied that the rate $n^{-1/d'}$ is optimal.

(2) The main focus of our work is on the theoretical side. The experiments can be seen as a proof of concept to overcome the curse of high dimensionality in the Wasserstein accuracy bound. We add more experiments on the basic yet essential statistics of the synthetic data, including mean and covariance.

(3) We agree the empirical accuracy gets worse when $\varepsilon$ is small. We add some explanation for the behavior of low-dimensional algorithm in Section 5. When $\varepsilon$ is small, $(\varepsilon n)^{-1/d'}$ cannot leverage the strength of low-dimensional projection and hence introduce some unnecessary errors. One possible approach is to enlarge the dataset.

Also, optimizing the algorithm more practically could potentially increase its performance. However, it is not the main focus of our work in this paper.

Questions

(1) The empirical comparison is in our simulation. The work of He et al. (2023) has no PCA step, and the low-dimensional improvement significantly improves the accuracy and overcomes the curse of high dimensionality.

(2) Thank you for the suggestion. $\delta_{X}$ denote the point mass measure at $X$ and hence $\mu_{\mathcal{X}}$ is the empirical measure for ${\mathcal{X}}$. We will clarify the definition.

(3) Whether the original data is exactly or approximately low-dimensional will only influence the first error term, the singular value term in the main theorem, Theorem 4.2. This term would decrease if the data is near a certain $d'$-dimensional subspace, and it would vanish when the original data is actually low-dimensional. Therefore, one can tell from the singular value term if the current $d'$ is a good choice. We add details in Appendix E about the method to choose $d'$ adaptively and privately.

(4) There isn't a tight lower bound for the private low-dimensional synthetic data. However, the general lower bound of private synthetic data (Boedihardjo et al. 2022) is applicable. When data is actually low-dimensional, our upper bound agrees with the lower bound because one can regard the original data as a dataset on the corresponding subspace. When data is not low-dimensional, by the general lower bound, it is impossible to get a result better than $O(n^{-1/d'})$. However, although the singular value term is reasonable due to the PCA step, it remains unknown whether it is necessary for low-dimensional synthetic data.

Weakness

Thank you for your comments.

(1) The main focus of our work is on the theoretical side. We do not run extensive experiments to test the utility of the data. The experiment can be seen as a proof of concept for the Wasserstein accuracy bound we proved. As a result, the low-dimensional algorithm does overcome the curse of high-dimensionality and significantly improves the original algorithm in both accuracy and time and space complexity.

(2) Indeed, the goal of our algorithm is to ensure the utility of the synthetic data in various down-streaming tasks. We add the comparison of some more basic yet essential statistics of the dataset, including the mean and the covariance, in Appendix~F.

(3) Thank you for the suggestion. The main idea of our approach is to generate a private subspace and create private coordinates after projecting data onto that private subspace. We add a non-technical summary of the algorithm in the introduction.

Questions

(1) We ran the algorithm in different scales of privacy parameter $\varepsilon$ in Figure 2. For Figure 1, we set the parameter to be $\varepsilon=10$ to show that there are still some similarity points between the synthetic data and original data. % When $\varepsilon$ becomes smaller, the synthetic images are no longer recognizable, but training on synthetic data with smaller $\varepsilon$ still has a nontrivial generalization performance, as shown in Figure 2. We change the parameter of Figure~1 with $\varepsilon=4$, which is a reasonable choice in practice, and the accuracy remains good.

(2) Thank you for the question. We mentioned the Adaptive and private choices of $d'$ at Section 1.1. We will add a more detailed discussion for the choice of $d'$ in the Appendix E. The main idea for the choice of $d'$ is to balance different terms in the error bound of Theorem 4.2, by finding the best trade-off between low-rank approximation error from SVD and error related to privacy guarantee. Such a minimization problem would be time-efficient as we only need the values of the singular values of the private covariance matrix.

(3) Yes, by our Wasserstein distance bound we showed in Theorem 4.2, one can use the synthetic dataset output from Algorithm 1 for mean and covariance estimation and many other statistical inferences by taking a different Lipschitz test function $f$ in the Kantorovich-Rubinstein Duality expression of Wasserstein distance. The information of Kantorovich-Rubinstein duality of $W_1$ is included in Appendix A.