LabelDP-Pro: Learning with Label Differential Privacy via Projections

We appreciate your insightful discussion. We were encouraged that you found our method “cute”, and we achieved “A good balance between theory and experimental results, which is a good fit for ICLR”. Here we address your detailed comments, which are helping us revise the paper and chart out future directions.

Q1. Theoretical contribution

I think the comparisons in the theoretical part need to be clear, i.e., what's the exact gain of the proposed method?

A: We thank the reviewer for this question. The goal of the theoretical section is to study the theoretical convex setting to build intuition for the general case of deep neural networks (which are beyond the reach of current theoretical frameworks). The goal is to provide some intuition for how LabelDP-Pro with different denoisers might compare to each other; in fact, the analysis of this setting is precisely what guided us to try the different denoisers that we do, but this section is by no means supposed to a complete explanation for the empirical results. Note that we provide the following caveat in the last paragraph of Section 4, “Note that the bounds in Table 4 hold only for convex loss functions. Moreover, they are upper bounds on the excess error. For instance, while the bound in Lemma 3 is tight in the worst case, better rates might be achievable under additional assumptions on the loss function. Despite these limitations, we see in Table 4 that the excess error bounds align well with the experimental findings.”

Q2. Non-applicability of Subsampling for SelfSpan

If I understand it correctly, the problem is that even though the additional projection step does not touch sensitive data (labels) in this case, one cannot directly use post-processing. This is because the projection will leak the index of the sampling result, which then impacts the privacy amplification by subsampling in the original DP-SGD. Due to this, when using SELFSPAN, one cannot enjoy the gain/benefit of subsampling. On the other hand, since it does not touch labels, one can still use post-processing over the non-subsampling version of DP-SGD?

A: Yes, indeed this is correct.

Label-DP Pro using Self-Span projection can be viewed as a post-processing of non-subsampling version of DP-SGD, whereas Label-DP Pro using Alt-Span denoiser can be viewed as a post-processing of the subsampled version of DP-SGD. Perhaps a simple way to see this is as follows. Consider the following two mechanisms:

1. Mechanism $M_1$ that reveals, for each training step, just the noisy average gradient for the batch $I^G$ (without revealing $I^G$). Amplification by subsampling applies in this case.
2. Mechanism $M_2$ that reveals, for each training step, the entire unlabeled batch $I^G$ along with noisy average gradients for that batch. Amplification by subsampling does not apply in this case.

DP-SGD and LabelDP-Pro with Alt-Conv denoiser can be viewed as a post-processing of $M_1$, since in the latter, the projection operation only uses non-private information, namely the alt-batch $I^P$.

On the other hand, LabelDP-Pro with Self-Span / Self-Conv denoisers cannot be seen as a post-processing of $M_1$, but can still be seen as a post-processing of $M_2$.

We would like to extend our gratitude to the reviewer once again for their constructive feedback.

Did our responses resolve the reviewer's concerns regarding the clarity of our theoretical results? Given that this appears to be the reviewer’s primary concern, we would like to ensure that we address it before the rebuttal deadline (Nov 22nd). We are also open to continuing discussions and welcome any further comments.

We appreciate the reviewer’s insightful feedback. We were encouraged that you found our method novel and our arguments well-explained. Here we address your detailed comments, which are helping us revise the paper and chart out future directions.

Q1. Concerns about the accuracies

The pure DP-SGD can be much better, which can potentially bring benefits for the proposed algorithm. For example, De et al., 2022 empirically show that DP-SGD can achieve 56.8% accuracy on CIFAR10 when eps=1.0 , while the number reported in the paper is only 43.5%.

ALIBI's accuracy on CIFAR-10 is reported as 51.3 when eps=1.0 in Table 5 in the paper, while in the original paper (Malek et al. (2021)) ALIBI achieves 71% when eps=1.0.

A: Thanks for the comments! It is worth noting that the differences in accuracy between our results and those reported in previous studies can be attributed to the choice of a simpler convolutional network (see Table 10.b in Appendix D) as opposed to the ResNet used in earlier work. This variance in backbone models was driven by efficiency considerations, given our large-scale evaluations across multiple settings and benchmarks.

However, as our method builds upon DP-SGD and reduces the noise it injects; if the baseline DP-SGD accuracy improves, we shall be able to achieve better accuracy. For instance, as shown below, when we switch to a more complicated network (with 4 more Conv layers), DP-SGD, ALIBI and our method all achieve higher performance, while our method is still able to retain the improvement for small $\varepsilon$’s.

Q2. Comparison w/ PATE-FM

When leveraging self-supervised learning with LabelDP, PATE-FM doesn't utilize the SelfSL on CIFAR-10, which seems a little unfair. It is reasonable to at least utilize a pretrained feature extractor as an initialization instead of random initialization when training teachers in PATE-FM. In this way, PATE-FM leveraging SelfSL is expected to have better accuracy.

A: Thank you for raising this concern. We want to clarify that while PATE-FM does not incorporate Self-Supervised Learning (SelfSL), its Semi-Supervised Learning (SemiSL) pipeline achieves notably higher accuracy (95.5% non-private accuracy) compared to the SelfSL pipeline we used in our evaluation, which achieves 90.9% non-private accuracy. This observation suggests that their backbone model is, in fact, stronger than our model.

It is important to note that even though PATE-FM utilizes a more robust backbone model, our LabelDP-Pro approach continues to outperform PATE-FM in the high-privacy regime (see Table 6, $\varepsilon \leq 0.5$).

We would like to extend our gratitude to the reviewer once again for their constructive feedback.

Did our responses resolve the reviewer's concerns regarding 1) the accuracy when using a stronger backbone model, 2) our comparison with PATE-FM, and 3) the discussion and comparison with previous work? Given that they appear to be the reviewer’s primary concern, we would like to ensure that we address them before the rebuttal deadline (Nov 22nd). We are also open to continuing discussions and welcome any further comments.

Results for moderate and large epsilon

Thanks for your clarification and explanation. I think the large gap between the proposed method and existing methods in the medium to low privacy regimes is still my biggest concern. If the method is only marginally inferior to the baselines for $\varepsilon>1$, I would be much more supportive of this work as it proposes a new projective gradient method for Label DP. My opinion remains unchanged for now.

Comments on user-level privacy

I do not quite agree with the argument that "practical applications of user-level DP cannot go beyond group privacy". Many works in federated learning have integrated user-level privacy. See Figure 2 in [1] and a more recent work of [2]. I don't think any of these works use a simple application of group privacy. These works apply minibatch gradients in DP-SGD/ DP-Fed-Avg for each user, replacing per-example gradients in standard item-level DP-SGD, which should naturally provide user-level privacy guarantees. Using a per-batch gradient would help reduce the variance, which is precisely the important intuition that was used in the three theoretical works you mentioned.

Moreover, the experiments you have demonstrated for user-level DP have no more than 10 samples per user, which is far from practical. Even with such a small $k$, we can also see as $k$ increases, the performance actually drops, which is another empirical evidence that group privacy is highly sub-optimal. I am curious about what happens when k is slightly larger, say 100, which is very common in practical scenarios. I view this part of the result more as a demonstration of good performance for very small epsilon, rather than an independent and novel contribution to user-level differential privacy.

[1] Practical and Private (Deep) Learning Without Sampling or Shuffling, Kairouz et.al. ICML 2021 [2] Learning to Generate Image Embeddings with User-level Differential Privacy, Xu et.al, CVPR 2023

We appreciate your insightful input. We were encouraged that you found our method simple yet practical, and our empirical results encouraging. Here we address your detailed comments, which are helping us revise the paper and chart out future directions.

Q1. Sub-optimal choice for group privacy

The user-level private algorithm only leverages group privacy, which is extremely sub-optimal even in the simple problem of mean estimation. A good user-level private algorithm should go beyond the simple application of group privacy.

A: We appreciate this comment. We would like to note that we ensure a fair comparison among all methods by employing the same group privacy rule for all approaches. Furthermore, we evaluated our approach not only with user-level privacy (Section 6), we also showed that it consistently outperforms the baselines in item-level privacy settings (Section 5).

We would also like to note that, while there are many recent results on user-level privacy that go beyond group privacy [1,2,3], none of the results are practical as far as we can tell (e.g. in the use of the i.i.d. or other assumptions on the data). This is demonstrated by the lack of empirical evaluations in these works. We would appreciate it if the reviewer could provide further clarification or pointers to prior work on practical user-level privacy that goes beyond simple group privacy.

[1] Daniel Levy, Ziteng Sun, Kareem Amin, Satyen Kale, Alex Kulesza, Mehryar Mohri, Ananda Theertha Suresh. “Learning with User-Level Privacy.” https://arxiv.org/abs/2102.11845

[2] Esfandiari, Hossein, Vahab Mirrokni, and Shyam Narayanan. "Tight and robust private mean estimation with few users." https://arxiv.org/abs/2110.11876

[3] Badih Ghazi, Pritish Kamath, Ravi Kumar, Raghu Meka, Pasin Manurangsi, Chiyuan Zhang. “On User-Level Private Convex Optimization.” https://arxiv.org/abs/2305.04912

Q2. Performance for moderate level of privacy

For eps>=1 in Tables 5 and 6, the proposed algorithm underperforms the best baseline by a large margin. In practice, it is still reasonable to use eps<5, so it would be better if the algorithm could also perform well for moderate level of privacy.

A: We appreciate this comment. We’ve explained why we consider the high-privacy regime in our general response. In short, this consideration results from the intrinsic definition of DP and practical requirements for stronger privacy guarantees, as well as the unsatisfactory performance of existing LabelDP baselines.

Furthermore, we note that in user-level privacy applications (as detailed in Table 7), our approach continues to outperform the baseline for medium-level privacy with $\varepsilon=5$, which demonstrates the versatility of our method in delivering competitive utility even in scenarios where a moderate level of privacy is required.

Q3. Explanation for inferior performance for eps>=1

Could you explain why the proposed algorithm underperforms the best baseline by a large margin when training from scratch for eps>=1

A: Thanks for this question. A possible explanation for this is that the excess variance in the gradients introduced by randomized response decreases exponentially as ε increases beyond 1. On the other hand, in DP-SGD, the excess variance in the gradients decreases at best only polynomially $1/\varepsilon^{O(1)}$. This is analyzed formally in the case of convex optimization in Table 4 of our submission. This distinction can provide an explanation of why our method, which is built on DP-SGD, outperforms baseline methods utilizing randomized response in the low-ε regime but exhibits inferior performance in the high-ε regime.

Q4. SSL outperforms trained from scratch

When using pre-trained weights from SSL, the result for eps>1 is much better. Maybe this is due to a more accurate gradient subspace after SSL pretraining?

A: Thank you for this question. Yes, the accuracies achieved under SSL (Table 6) are higher than those achieved when trained from scratch (Table 5), which could be attributed to better image representations learnt by SSL and thus resulting in a more accurate gradient subspace.

1. On high v.s. low privacy

I think the large gap between the proposed method and existing methods in the medium to low privacy regimes is still my biggest concern. If the method is only marginally inferior to the baselines for $\varepsilon>1$, I would be much more supportive of this work as it proposes a new projective gradient method for Label DP.

A: Our method serves as a better LabelDP option in high-privacy regimes. However, it's worth noting that developers retain the flexibility to choose SOTA methods for low-privacy regimes. Furthermore, we have conducted an empirical study on the point of intersection (as detailed in Appendix D.4), which can serve as a reference for making decisions about which method to deploy.

Furthermore, we wish to point out that it is common for different DP algorithms to be better in different regimes of parameters. For example, for linear queries, there are three pure-DP algorithms which are better for different regimes of parameters; see Theorem 1 in [A].

References: [A] Aleksandar Nikolov: Private Query Release via the Johnson-Lindenstrauss Transform. SODA 2023: pp. 4982-5002.

2. On user-level privacy

I am curious about what happens when k is slightly larger, say 100, which is very common in practical scenarios.

A: Below we present the results for $k=100$. As shown, our method consistently outperforms RR and DP-SGD under $k=100$.

I do not quite agree with the argument that "practical applications of user-level DP cannot go beyond group privacy". Many works in federated learning have integrated user-level privacy. See Figure 2 in [1] and a more recent work of [2]. I don't think any of these works use a simple application of group privacy. These works apply minibatch gradients in DP-SGD/ DP-Fed-Avg for each user, replacing per-example gradients in standard item-level DP-SGD, which should naturally provide user-level privacy guarantees.

A: We appreciate the reviewer’s prompt response and for providing the references. We would like to clarify that what the reviewer suggested is exactly our implementation for user-level DP-SGD and LabelDP-Pro. We use group privacy only for RR-based methods. We apologize for any lack of clarity in our initial submission, and for the confusion in our previous response.

We agree with the reviewer and have observed that opting for group privacy results in a decrease in performance for these two gradients-involved methods. This indeed underscores another advantage of our approach, as it is compatible with a more effective user-level privacy implementation.

We have updated our submission to reflect these details more explicitly (Section 6) and have also included the provided references.

We appreciate your insightful comments. We were encouraged that you found our method novel and acknowledged our improvement over SOTA. Here we address your detailed comments, which are helping us revise the paper and chart out future directions.

Q1. Concerns about targeting high-privacy regime

Developers will prefer a medium privacy regime with very close to non-private utility compared to a highly private regime with very low utility. From the paper results, trends suggest that the proposed algorithm gets inferior to SOTA as epsilon starts to pass 1 which I think is the most important hurdle in using the proposed algorithm in practice.

A: We appreciate this comment. We have explained why we consider the high-privacy regime in our general response. In short, this consideration results from the intrinsic definition of DP and practical requirements for stronger privacy guarantees, as well as the unsatisfactory performance of existing LabelDP baselines.

Furthermore, we note that in user-level privacy applications (as detailed in Table 7), our approach continues to outperform the baseline for medium-level privacy with $\varepsilon=5$, which demonstrates the versatility of our method in delivering competitive utility even in scenarios where a moderate level of privacy is required.

Q2. Results for moderate level of privacy

I would like to see results of the proposed algorithm for epsilons between 1 and 10 too (for a fairer comparison and decision making for interested users).

A: Thank you for your suggestion. Please find below the results for $\varepsilon$ values ranging from 0.05 to 10, with the best accuracy for each $\varepsilon$ highlighted in boldface. However, it is important to note that our method primarily focuses on achieving high privacy (i.e., the low-$\varepsilon$ regime). As a result, the relatively lower performance in larger $\varepsilon$ values is expected and has been explained in the theoretical analysis presented in Section 4 of our submission.

Q3. Empirical epsilon study

I would like to see an empirical epsilon study (like the one referenced by authors, e.g. Malek et al. 2021)

A: Thank you for your suggestion. While we acknowledge the importance of privacy auditing and empirical privacy studies, it appears to be outside the scope of our current work. We intend to consider this for future research endeavors.

Q4. Results on CIFAR-100

I would like to see studies on CIFAR-100 (along with a comparison with SOTA)

A: We appreciate this suggestion and are working on gathering these results. We will try to share them in a later post.