Differentially private optimization for non-decomposable objective functions

Thanks for the review!

1. While our proof indeed utilizes triangle inequalities, our core contribution lies in the careful decomposition of the terms. This decomposition, achieved through a combination of the chain rule and well-chosen inequalities, enables to bound specific terms balancing the sensitivity while maintaining more signal to noise ratio than NaiveDP. This improvement is not merely a technical artifact; it has real implications for practical applications.

   Moreover, we demonstrate this improvement both theoretically and empirically. Corollaries 4.5 and 4.6 provide theoretical guarantees for the performance gains, while our experiments further validate these findings in practice. Furthermore, Theorem 4.2 is not just a specific technical result. It generalizes to a broader class of non-decomposable loss functions (unexplored by the DP community), extending the classic DP-SGD with per-example clipping. This generalization is a significant contribution, as it expands the applicability of differential privacy to a wider range of machine learning models and tasks.

2. The reviewer may have missed Example 2.3., where we detail why batch clipping is not efficient with contrastive losses. Indeed, per-example (or per-pairwise) clipping is not the only way of achieving privacy since the sensitivity can be more easily bounded with batch clipping. However, per-example clipping is essential to obtain high utility private models. As we note in Section 2.3., summed losses noise scales as n with batch clipping and only constantly with our procedure. Empirically this is also observed in our experiments, where naive-DP performs batch clipping.

3. Thanks for raising this subtlety. We work with summed losses as this notation is more easy and is conventional in the DP community (See Bassily et al 2014).

   More crucially, this convention highlights the advantages of our method. When the objective function is expressed as the average of per-example losses, batch clipping adds constant noise while the noise magnitude of our approach decreases with larger batch sizes as n grows. This scaling is a key benefit of our technique, leading to improved performance with large batches.

   It's also worth noting that while the sensitivity (and thus the noise magnitude) can change depending on the formulation of the loss function, the differential privacy guarantee itself remains unaffected.

4. Thanks for raising this concern. This tradeoff is a central theme throughout our paper. Our core contribution is precisely addressing this tradeoff by proposing a clipping method that significantly reduces the amount of noise required for a given privacy guarantee. We demonstrate this improvement both theoretically and empirically:

   • Theoretically: Our sensitivity analysis shows that our clipping scheme has constant sensitivity, while traditional batch clipping increases linearly with the batch size n. This directly translates to a significant reduction in the standard deviation noise for the same privacy guarantee.

   • Empirically: Our experiments show that our method achieves significantly better utility compared to naive DP (batch clipping) for the same privacy level. In some cases, batch clipping leads to catastrophic performance degradation, highlighting the severity of the privacy-utility tradeoff with existing methods.

We appreciate the reviewer's feedback, although we respectfully disagree with their assessment of our work.

The reviewer states that our derivations are trivial and that the resulting algorithm is a “simple” variation of DP-SGD. However, the challenge of adapting differential privacy to non-decomposable loss functions (such as contrastive loss) has been a significant blocker in the field. Previous research has often circumvented this issue altogether (Xu et al. 2022, Li et al. 2022, Yu et al 2023), potentially missing out on the advantages of unsupervised learning approaches.

Our work directly addresses this challenge by carefully analyzing the derivative of the general non-decomposable losses and deriving its sensitivity. This analysis involves a non-trivial decomposition using the chain rule and the identification of specific conditions for generalizable non-decomposable loss functions. We then provide concrete examples and applications for widely used losses like the contrastive loss and the spreadout regularizer.

Regarding our algorithm being a “simple” variation – while many DP breakthrough algorithms build upon existing mechanisms the specific application and subtleties of implementation can be complex. For example, the exponential mechanism (See Dwork & Roth 2014) is an easy to describe mechanism, but sampling from it can be computationally hard. Similarly, the well known K-norm mechanism’s applicability is instance specific, and recent works (e.g. Joseph & Yu 2023) demonstrate the ongoing efforts in refining it for simple problems like sum and count queries. Our work makes a significant contribution by enabling the use of contrastive loss for training with sensitive data, opening up new possibilities in areas like medical image diagnostics.

We encourage the reviewer to re-examine our work; we believe that a deeper analysis will reveal the non-trivial nature of our contributions.

Additionally, we have carefully reviewed our manuscript and corrected the typographical errors and inconsistencies pointed out by the reviewer.

Let us know if you have precise questions you would want us to address.

Thanks for the review!

1. Thanks for the suggestions, we’ve included the notation change into Algorithm 1 in the revised version.

2. We would like to clarify that our experiments indeed evaluate unsupervised private pre-training, both in terms of the pre-training objective itself (Section 5.1) and its impact on downstream tasks through fine-tuning (Section 5.2). Fine-tuning is a standard practice in evaluating pre-trained models, as it demonstrates the effectiveness of the learned representations on different downstream tasks.

3. We acknowledge the popularity of language models. While our work primarily focuses on computer vision, the theoretical contributions and the proposed method are applicable to a wide range of input data, including language modeling. We chose to focus on computer vision due to its significant impact in various fields that deal with sensitive data, such as medicine. We believe that demonstrating the effectiveness of our method in image data showcases its importance and broader applicability. We emphasize that our theoretical results hold for any type of input data, including those used in language models.

Minor.

1. While we could provide a more comprehensive summary of our contributions, the content leading up to section 4 (notation, naive clipping, and example losses) is necessary to motivate the contributions.

2. This is a great point, thanks for the recommendation, We’ve updated the title and added a comment in section 4.2. Line 3 of Algorithm 1, the for loop counting is incorrect.

3. Thank you for catching this. The corrected sequence is $t=1,2,\ldots,T-1$.

Thanks for the review!

W1.

Both SimCLR and InfoNCE are indeed within the scope of our analysis.

• SimCLR uses the canonical contrastive loss, which corresponds with Definition 2.2 in our paper. We already explicitly state this connection after the definition and provide sensitivity bounds in Lemma 4.5.
• InfoNCE: While incorporating a context variable, InfoNCE's core loss function and batch sampling strategy still fall under the framework of Definition 2.2.

We have included references to both SimCLR and InfoNCE in the Introduction, Related Work, and Preliminaries sections.

W2.

• We understand the importance of thorough comparisons. However, we deliberately excluded BatchNorm layers from our models due to their inherent incompatibility with privacy preservation. Our focus is to rigorously analyze the impact of clipping and noise on unsupervised private learning. Introducing BatchNorm would blur the effects of these crucial components, making it difficult to isolate their individual contributions.

    This focused approach provides insights into the core challenges of private contrastive learning. While a comparison with models that include BatchNorm layers might be interesting in other contexts, it falls outside the scope of our current paper.

• LayerNorm is not designed for privacy preservation. It normalizes across features within a single sample, ensuring that each sample is processed independently. This makes it easier to integrate with differential privacy techniques, as it avoids the aggregation of sensitive information across different samples. In contrast, BatchNorm normalizes a single feature across multiple samples in a batch. This aggregation of information across samples can potentially leak private information, making it more challenging to combine with differential privacy mechanisms.

    Privacy implications of both LayerNorm and BatchNorm are still being actively explored within the differential privacy community (see [1, 2] below) , LayerNorm's sample-wise operation is inherently more compatible with DP techniques.

    [1] Davody, A., Adelani, D. I., Kleinbauer, T., & Klakow, D. (2020). On the effect of normalization layers on differentially private training of deep neural networks. arXiv preprint arXiv:2006.10919.

     [2] Ponomareva, Natalia, et al. "How to dp-fy ml: A practical guide to machine learning with differential privacy." Journal of Artificial Intelligence Research 77 (2023): 1113-1201.

• Bounds are actually provided for naive-DP and non-private but these bounds are miniscule when compared to logit-DP (e.g., zooming into the plots, you can see some shaded regions for non-private around the 180K examples mark).

      We have updated the absolute metrics in Appendix B with standard deviations.

• Our primary objective in these experiments is to provide a clear demonstration of the theoretical and performance advantages offered by our proposed method. More specifically, we aim to showcase its potential for performance improvement within a constrained experimental setup. Consequently, the chosen stopping criteria for each experiment aimed to clearly demonstrate the loss improvement offered by our method compared to previous baselines across different settings. These results, even with a limited number of training epochs, effectively illustrate the performance boost achieved by our method.

      We acknowledge that our chosen training regime deviates from typical practices for training for several epochs. This choice was deliberately made to prioritize efficiency in computational resources, especially given that this work focuses on the validation of our theoretical contributions.

      Moreover, note that the difference between the number of training epochs between pre-training and fine-tuning is not a direct comparison since pre-training utilizes different batch sizes optimized for each considered method. Larger batch sizes often allow for faster convergence, potentially requiring fewer epochs.

• We acknowledge that the accuracy scores for the CIFAR100 fine-tuning task are lower than typically observed. As mentioned above, our goal was to demonstrate the advantages of our proposed method, namely that we introduce a method that is able to overcome the loss stagnation of current contrastive loss methods, rather than training until state of the art results. This choice was to balance computational efficiency and save resources effectively, as it is clear from the plots that other methods are underperforming.

5. No need to train to the state-of-the-art. Just to ensure that the Relative Loss Value for Logit-DP will be the best during the whole run. See 4)

We have included these results (Figure 6) and demonstrate that Logit-DP consistently outperforms Naive-DP in terms of relative loss throughout the entire training process.

C2 is still unaddressed.

We apologize for this oversight. We have corrected the title to accurately reflect "CIFAR100."

partially addressed W2 (regarding the bound on the plot at 180K examples mark) and have added a part of my correction to the text.

We believe we have now fully addressed W2.

The absence of at least one comparison with BatchNorm layers, one full training for 100+ epochs on CIFAR10

These have now been included in the revised manuscript, see Table 3 and Figure 6 in the appendix.

Summary

We believe this revised manuscript comprehensively addresses the reviewer's concerns. We have clarified the inherent incompatibility of standard BatchNorm with differential privacy, provided further experimental results as requested, and corrected the minor errors noted. We are confident that our work makes a valuable contribution to the privacy field and the unsupervised learning field by making progress on differentially private optimization of non-decomposable objective functions.

References

[1] Davody, A., Adelani, D. I., Kleinbauer, T., & Klakow, D. (2020). On the effect of normalization layers on differentially private training of deep neural networks. arXiv preprint arXiv:2006.10919.

[2] Ponomareva, N., Hazimeh, H., Kurakin, A., Xu, Z., Denison, C., McMahan, H. B., ... & Thakurta, A. G. (2023). How to dp-fy ml: A practical guide to machine learning with differential privacy. Journal of Artificial Intelligence Research, 77, 1113-1201.

[3] Dosovitskiy, A. (2020). An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.11929.

[4] Kong, W., & Munoz Medina, A. (2024). A unified fast gradient clipping framework for DP-SGD. Advances in Neural Information Processing Systems, 36.

[5] Bu, Z., Mao, J., & Xu, S. (2022). Scalable and efficient training of large convolutional neural networks with differential privacy. Advances in Neural Information Processing Systems, 35, 38305-38318.

[6] Lee, J., & Kifer, D. (2021). Scaling up differentially private deep learning with fast per-example gradient clipping. Proceedings on Privacy Enhancing Technologies.

Thank you for the review!

1. You're correct that a naive approach would result in $B_{contrastive}$ being $O(n)$. However, in our proposed method, as the batch size $n$ grows, $B_{contrastive}$ converges to the constant $e^2$. As shown in (6), this is because $n$ is both in the numerator and denominator and the dominant term in $B_{contrastive}$ becomes independent of $n$ for large values. This contrasts with the naive scheme, where $B_{contrastive}$ does indeed grow linearly with $n$.

2. We now provide these graphs in Figure 5 in the appendix. While Logit-DP is computationally more expensive than Naive DP-SGD per-iteration, it is more efficient in terms of loss decay, as shown in Figure 5.

Questions

• We've incorporated your suggested missing references in the revised version, in Section 3, Related Work.

  In brief, Ponomareva et al. focus on efficient private pre-training for T5, which doesn't need usage of a non-decomposable loss. Yu et al. uses a model typically trained with a contrastive loss in non-private settings, but their approach substitutes it with a per-example loss. This leads to a loss of information from unlabeled data points and inter-sample correlations.

We have incorporated the suggested changes and clarifications into the revised manuscript. Additionally, the code associated with this work is now available in the supplementary material.