Choosing Public Datasets for Private Machine Learning via Gradient Subspace Distance

First, the results on CIFAR10 and FMNIST are achieved without pre-training---we DP train a Resnet20 from scratch. Second, we respectfully disagree with the argument that the utility gains are insignificant. For instance, when examining the results of ChestX-ray14 dataset, our approach demonstrates a significant ~3% accuracy improvement over the DP-SGD baseline. This improvement is particularly crucial in clinical environments. Furthermore, this paper's primary contribution lies in identifying and addressing an important scientific question: determining which public datasets perform well for specific private tasks. Our solution to this problem is both straightforward and highly effective.

We appreciate the reviewer for highlighting this interesting metric. Visually similar datasets may not always be the most suitable choice for private ML. For instance, while chest x-ray datasets like CheXpert provide utility gains, the Kneeos dataset, consisting of knee X-rays, also offers utility. Conversely, the MNIST-M dataset, which is similar to SVHN as they both consist of images of digits, provides the lowest utility. Task2Vec, a method known for measuring dataset similarity in nature, is unable to accurately rank datasets utility (refer to Section 6.4). Second, it is unclear if other metrics can also enjoy the same properties, i.e., ordering of GSD is preserved over training (Section 4.2), transferability (Section 6.3). That said, that is exactly the main contribution of this paper: we propose this metric, and validate that it is suitable for selecting the best public dataset via thorough empirical validations and some theoretical analysis.

We disagree that the finding is "trivial": indeed, if it were trivial, then it would always be true that using public data drawn from the same distribution as the private data would be ideal. However, in one of our more surprising results, we find this is not true -- that public data from a separate distribution may be better than the original one! For example, CIFAR-100 is consistently a better dataset for CIFAR-10 than itself, and this answers the reviewer’s question i). Furthermore, public data from the same distribution as the private dataset may not always be available: consequently, GSD is useful in determining which alternative dataset one should use. See another example: at first we also assume that MNIST-M (colorful MNIST), is a good public dataset for SVHN, as they are all images of digits. BUT GSD shows that MNIST-M is even worse than CIFAR-100!

Thank the reviewer for the feedback.

Weakness i

We agree with the reviewer's suggestion that a theoretical guarantee is needed for privacy, as our current guarantee is based only on heuristics. However, as discussed in our paper, for our scientific question, exploring which public datasets perform well for a particular private task, this is inconsequential. In our paper, we discuss some follow-up work that addresses how to select private datasets in a privacy-preserving manner. making it unclear if it can be considered as "knowing the utility in prior" due to the significant time cost. That said, we hope our work initializes further exploration into this scientific question and provides insights for future work that develops a practical method with rigorous DP guarantee.

Weakness ii

We appreciate the reviewer for pointing out this issue. We will revise and clarify this claim accordingly.

Weakness iii

We appreciate the reviewer's acknowledgment of the importance of our work's purpose. It makes sense that for most of the private datasets, the best public dataset is itself. However, our method also works when we only have accessible out-of-distribution data. We empirically validate this across various pre-conditioning/pre-training methods, datasets, model architectures, and number of available public examples. We also give theoretical analysis to explain why GSD can be a good indicator of public datasets utility. Furthermore, we demonstrate that GSD's transferability showcases its robustness. That said, we believe the current results presented in this paper are sufficient to validate the usefulness of GSD. Nevertheless, we are happy to discuss with the reviewer what kind of additional evaluation is needed to further validate the robustness of GSD.

Weakness iv

Considering it is now near the end of 2023, we believe, to the best of our knowledge, most works studying improving the utility of differentially private machine learning, turn to public data and end-to-end deep models[1][2][3]. Even the first author of the mentioned reference has shifted their research towards studying private machine learning with public data. Additionally, handcrafted feature extractors have limitations as they cannot generalize well to complex tasks. This is why researchers are turning to deep models and public data. Notably, the paper mentioned by the reviewer, includes a section titled "TRANSFER LEARNING: BETTER FEATURES FROM PUBLIC DATA".

[1] Da Yu, Huishuai Zhang, Wei Chen, and Tie-Yan Liu. Do not let privacy overbill utility: Gradient embedding perturbation for private learning. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL https://openreview.net/forum?id=7aogOj_VYO0.

[2] Yingxue Zhou, Steven Wu, and Arindam Banerjee. Bypassing the ambient dimension: Private sgd with gradient subspace identification. In International Conference on Learning Representations, 2021. URL https://openreview.net/forum?id=7dpmlkBuJFC.

[3] Ganesh, Arun, Mahdi Haghifam, Milad Nasr, Sewoong Oh, Thomas Steinke, Om Thakkar, Abhradeep Thakurta, and Lun Wang. "Why Is Public Pretraining Necessary for Private Model Training?." ICML 2023.

We appreciate the reviewer for proposing this interesting question. We are unsure if we understand the question, but we will attempt to provide an answer. Empirically, top singular values are usually larger. We have an empirical evaluation in Appendix D.2. Gradient subspace distance is bounded by $\sqrt{k}$, and is usually much smaller than top singular values. Theoretically, this question can be extended to “does singular value itself have a mathematical relation with the rank of the matrix?” To the best of our knowledge, we cannot find a good mathematical relation between these two quantities.

Please let us know if this answers your question. We are happy to discuss more.

The reviewer raises an interesting question: how will GSD reflect the similarity between data sets in nature? GSD is designed to rank the utility of potential public data sets in the context of private machine learning. Thus, it is natural to think that data sets that are semantically close, or say similar in nature, will have smaller GSD, meaning higher utility. However, our experiments show that this is not always true. We surprisingly find that CIFAR-100 is even ‘closer’ to SVHN w.r.t. gradient subspace distance, compared with MNIST-M (colorful MNIST). But in nature, MNIST-M should be closer to SVHN than CIFAR-100, as MNIST-M and SVHN are all images with digits. On the other hand, Task2Vec, the method we compare GSD with, is good at describing data set similarities in nature, but fails to give correct predictions for the utility w.r.t. private machine learning.

That said, it is natural to think that smaller GSD means two data sets are more similar in nature. But this isn’t always true, and vice versa: two naturally similar data sets may not have smaller GSD. For example, CIFAR-10 should be most naturally similar to itself, but our experiments show that CIFAR-100 gives the smallest GSD. Again, the idea of GSD is to rank the utility of a list of potential public data sets in the context of private machine learning, and GSD is effective in doing so.

We acknowledge that GSD is indeed not differentially private, and thus may leak sensitive information. We give the following reasons to explain that 1) GSD is unlikely to breach privacy in practice, and 2) this work still makes meaningful contributions

• The selection of a public dataset is a hyperparameter: in essentially all work on private ML, hyperparameter tuning is performed non-privately, since the privacy impact is considered to be minimal [1][2].
• Under this suggestion, in the context of public data sets selection, we assume what an adversary can know from GSD is “CIFAR-100 is the chosen public dataset for CIFAR-10”. Since this provides little information to the adversary, we also assume an unrealistic adversary that knows: 1) the model used by GSD and all related computations, such as gradients and hidden layer activation, and 2) 90% of the private data examples used by GSD, along with all the remaining private examples in the dataset. The adversary attempts to use membership inference attacks to determine if a particular image $x_i$ is used by GSD (if $x_i$ is in the remaining 10%). When we apply a well-studied and well-cited white-box membership inference attack, the experiments show that even under this overly powerful adversary, the attack success rate is as good as random guesses (see Appendix D.1 for more details).
• We believe the main contribution of this paper is: identifying this scientific question (exploring which public datasets perform well for a particular private task), and giving a simple yet effective solution.
• Nevertheless, we discuss DP methods for GSD computation in Appendix C. We hope that this work will serve as a starting point and inspire future research to effectively solve this scientific question with differential privacy.

[1] Nicolas Papernot and Thomas Steinke. Hyperparameter tuning with renyi differential privacy. In Proceedings of the 10th International Conference on Learning Representations, ICLR ’22, 2022.

[2] Shubhankar Mohapatra, Sajin Sasy, Xi He, Gautam Kamath, and Om Thakkar. The role of adaptive optimizers for honest private hyperparameter selection. In Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, volume 36 of AAAI ’22, pp. 7806–7813, 2022.

Thank you for the detailed questions, they help us to understand deeply. Below, we respond to your specific question.

GSD

• GSD only needs top-$k$ basis, i.e., let $p$ denote the model dimension, then $V_{pub}$ is $R^{p \times k}$. Here $k << p$, like if $p$ is $O(10^5)$, k is $O(10^1)$ or $O(10^2)$.
• Previous research has provided effective methods for computing the top-$k$ basis. Like, PyTorch has the built-in function torch.svd_lowrank, which uses randomize SVD to compute top-$k$ basis. For a simple theoretical analysis, we assume that the model used for GSD is a linear model with one hidden layer of size $n$, the number of examples are $m$, the input dimension is $d$, the output is of size $c$, and the lower dimension is $k$. Then the time complexity of GSD is $O(2mdn + 2mnc + 2m(dn+nc)\log(k) + 2(m+dn+nc)k^2)$. Here, $O(mdn + mnc)$ is the time cost for computing the gradient matrix and $O(m(dn+nc)\log(k) + (m+dn+nc)k^2)$ is the time cost for computing $V_{pub}$. We can see that computing $V_{pub}$ takes a longer time than computing gradient matrix, but only scales by a small factor w.r.t $k$.
• In our implementation, considering the fact that GSD computation only requires negligible time anyhow, we turn to PyTorch Reduced SVD torch.linalg.svd for its better implementation. Here, the time complexity of computing $V_{pub}$ is $O(m(dn+nc)r)$, where $r$ is the rank of the gradient matrix. Empirically, we re-run the 41s LoRA experiments mentioned before. Computing $V_{pub}$ and $V_{priv}$ takes around 35s. This is slightly off from the previous analysis, as we are expecting this time cost to be a little bit shorter. We guess it is possibly due to PyTorch's SVD implementation not being as efficient as backprop on GPU.
• Additionally, GSD itself only requires negligible time, mainly because of its one-pass computation.

Projection methods

• We borrow the complexity analysis from the GEP paper here. GEP uses power iteration to effectively compute top-$k$ basis. Let $k$ denote the lower dimension, $m$ be the number of public examples, $n$ be the size of private dataset and $p$ be the model dimension. The computation cost of one power iter: $O(2mkp + pk^2)$. The authors also use parameter grouping to reduce this computation cost to $O(2mkp/g + pk^2/g^2)$, where $g$ is the number of groups.
• For computing the clipped gradient, we borrow the analysis from this paper [BWZK22]. Using regular DP-SGD, computing a clipped gradient (one forward and one backprop) will take approximately $O(14mp)$. While computing the top-$k$ basis is less time-efficient than regular DP-SGD, the time cost won't increase significantly in practice since $k << p$.

We again thank the reviewer for the follow-up question. It also helps us gain a better understanding of GSD and projection methods. The analysis provided is rough and may be incorrect. We are open to discussing this further with the reviewer.

[BWZK22] Z. Bu, Y.-X. Wang, S. Zha, and G. Karypis, “Differentially private optimization on large model at small cost,” arXiv [cs.LG], 2022.

Thanks for clarifying that your main contribution is not with respect to anything on matrix perturbation theory; however, the idea of using cosine similarity to measure the closeness of two subspaces is not new. It is a crucial scientific question that has been raised a long time ago. So, I am still unsure how this is anyhow a "new" question.

Using Davis-Kahn type results is pretty common in understanding low-rank structure. As I mentioned earlier, there is a rich literature on it in various disciplines of applied mathematics. AFAIK, even in privacy, results like "Beyond worst case for singular value computation" and its follow-up work by Hardt-Price, and "Analyze Gauss" and its follow-up based on Dyson Brownian motion also use such similarity to study how close the span of the space is.

Finally, I still do not understand how measuring bounding the spectral norm of error with Frobenius norm of related object is anyhow meaningful. If you want to prove a bound, you would like to impose similar metric. Spectral norm approximation is traditionally harder (even from the streaming literature) because you are trying to bound the error with respect to $\sigma_{k+1}$ instead of $\sum_{j \geq k} \sigma_{j}$. That is why results like Kapralov-Talwar and Achliptas-McSherry (in privacy) is beautiful and the space required for such an approximation even without privacy is linear in dimension. When you use spectral norm as a metric on one side and Frobenius norm on the other side, you end up comparing apples with oranges.