Beyond Laplace and Gaussian: Exploring the Generalized Gaussian Mechanism for Private Machine Learning

We thank the reviewer for their time and respond to points below (in 2 comments).

Thank you for pointing the paper from Awan and Dong (2022) to us, we now incorporate it into the updated paper. Generally we do not believe there are any conflicts between the works; instead both complement each other and point to the same direction – DP could gain a boost from a correctly tuned noise distribution. More in-detail analysis of the differences is given below:

• The work by Awan and Dong is both important and very impressive, but our works differ in some key ways. Their work is an important work exploring the theoretical foundations of privacy mechanisms, but does not actually answer the question of what mechanisms are optimal for private machine learning.
• While Canonical Noise Distributions (CNDs) are a great notion, they are fundamentally a privacy guarantee, and do not make a claim about the utility of a mechanism. Our work looks at the privacy-accuracy tradeoff in machine learning for a family of mechanisms - something otherwise minimally studied. While intuitively it may seem that the CND should be an optimal mechanism because they minimize noise added for a given f-DP trade-off function, this assumes that all parts of the tradeoff functions are equally valuable to the utility. Imagine a utility function that strongly punishes outliers - in that setting, you want a mechanism that minimizes noise above some level, rather than more than one that minimizes total noise. We explore this in Appendix B.5.
• Proposition 4.2 and Theorem 4.3 only provide CNDs for l_infinity and l_1 bounds (respectively). L_infinity is an uncommon sensitivity, and not used in practice, while our own experiments using multivariate Laplace (GG for beta =1) lead us to believe that l_1 sensitivity with IID noise is suboptimal from an accuracy perspective.
• Privacy accounting is critical for tracking privacy during private ML. Their paper does provide theorems for composition of the CND mechanisms in f-DP, however, it remains unclear how to tightly compute the privacy of CNDs to compute an epsilon-delta bound using a known privacy accountant. Our work provides an accountant for each member of the GG family.
• Subsampling has been critical for making private ML applications work for reasonable privacy budgets. Their work does not directly consider how to compute the proper CND for the subsampled setting, nor how to do privacy accounting for subsampled variants of mechanisms based on CNDs.
• The two most useful DP formulations are GDP and F_{epsilon,delta}-DP. However, the paper does not build a CND for F_{epsilon,delta}-DP (Section 4.4) which is usable for ML. Their mechanism does not consider subsampling, and only considers the CND when using l_infinity sensitivity.
• They show that for Gaussian-DP, Gaussian mechanisms are CNDs. However, the GDP Accountant can significantly underreport the true \epsilon (https://arxiv.org/abs/2106.02848), and so unfortunately this does not directly translate into a useful application.

Below we address other specific comments in the review.

The paper's "Privacy Accounting for GG Mechanisms" relies heavily on numerical experiments without robust error control or rigorous proofs.

• We address the error of the privacy accountant in Appendix B.3. More specifically, Theorem 6 provides an error analysis of the privacy accountant, which provides an arbitrarily tight privacy accountant. (We set our acceptable tolerance for \epsilon to be 0.01, and round our reported values up to the nearest 0.01.)

The paper's focus on a single privacy budget ((\delta=10^{-5})) is both arbitrary and unconvincing. For instance, releasing a (10^{-5}) portion of the total data satisfies (\delta=10^{-5}) with (\epsilon=0), making it theoretically superior to all other mechanisms discussed in terms of this metric…. The experiments (PATE, DP-SGD) conducted under the privacy budget of (\delta=10^{-5}) are too limited to convincingly demonstrate the superiority of any specific (\beta) values. At this (\delta) setting, the noise variance added by the mechanisms varies widely, which is very likely to be the true reason behind the differing outcomes.

• We thank you for this comment, we actually run our DPSGD experiments with delta=1e-6. However, it appears that in our paper, we wrote 1e-5 in one place (Appendix E.2), as a vestige of a previous version. We have updated this, thank you for catching this.
• It’s worth also noting that presenting results for a single choice of delta= 1e-5 is standard for many DPSGD experiments. Two well-cited and well-regarded papers that achieve SOTA results use delta=1e-5 for CIFAR-10 https://arxiv.org/abs/2011.11660 and ​​https://arxiv.org/abs/2204.13650.
• Regarding the comment that at this delta, the variance varies widely. We are unsure what the reviewer is referring to, as the PRV accountant is correct to arbitrary precision.

[1/2]

We thank the reviewer for their time and comments. We respond to questions and weaknesses, separately below, starting with the questions. (We respond in 2 parts)

Is Theorem 1 saying there exists eps and delta for (eps,delta)-DP? Isn't it obvious that every mechanism has eps=1 and delta = 1 if I am not mistaken?

• You are correct that if delta is allowed to be 1, then all mechanisms are (epsilon, delta)-DP; however Theorem 1 states that there is an epsilon value for any choice of beta, sigma, and delta. While this seems intuitive in some cases it is certainly not true for all algorithms, and this precondition is a prerequisite to using the PRV Accountant. As an example, a mechanism that runs the \epsilon-DP Laplace mechanism with probability 0.9, and with the remaining 0.1 probability returns the non-noisy answer is (\epsilon, \delta)-DP for some \delta, but not for any delta < 0.1.

"However, unlike the results…. larger than beta> 3 " on page 8, is there any reason why this happens?

• First, we emphasize that the label accuracy decline is on the order of ~0.1%, and so this is not a significant drop. The drop is most noticeable specifically because of how little variance there is in the label accuracy across values of \beta. That said, we believe the drop is due to an artifact of how the mechanisms of equivalent DP guarantees are generated. To describe it in detail: first we add noise from an evenly distributed grid of \beta \in [1,4] and \sigma \in [0.01,7] values, and then we compute the privacy levels for those (\beta,\sigma) tuples and compute the corresponding mechanisms of approximately equal DP guarantees. Because of this, we overestimate \epsilon when solving for mechanisms with equivalent DP guarantees; this is most noticeable for larger choices of \beta, where the same difference in \sigma contributes to a larger \epsilon.

Is it reasonable to perform the comparison by fixing hyperparameters that are optimal in non-DP training?

• Previous work has shown that hyperparameters which are optimal in non-DP training are not necessarily optimal for DP training. This was explored in this work https://arxiv.org/abs/2007.14191, and a later work https://arxiv.org/abs/2110.03620 produced a scheme for how to do privacy preserving hyperparameter tuning.

For fixed hyperparameters, beta=2 is still near-optimal? or is it dependent on hyperparameters?

• In general, it is near optimal, but it does depend on the hyperparameters, we provide plots for this in Appendix E.3.

[1/2]

Thank the authors for the detailed response to my questions. I have a better understanding of your work now. The motivation and investigating the optimized $\beta$ in the GG mechanism are interesting and meaningful. Nevertheless, I still doubt if this paper is an ICLR-quality paper. The main reason is the lack of theoretical or rigorous supporting evidence for the claim ($\beta=2$ is near optimal). I understand that the analysis of the generalized GG mechanism on DP-SGD is quite problematic. However, even the empirical results in the paper are not sufficient in my opinion. For such a reason, I maintain my score.

We thank the reviewer for their response. We appreciate your feedback. Below we respond to the weaknesses stated in the review.

The experiments are conducted on fairly small datasets and deep learning architectures so it's hard to get a grasp of how well the generalized gaussian mechanism works.

• Unfortunately current research on private machine learning is still developing techniques for accurately training on larger datasets. The error contributed by differential privacy scales with dimension (https://arxiv.org/pdf/2106.00001.pdf), and larger datasets tend to require larger models to perform well. This is evidenced by the fact that the state-of-the-art results for CIFAR-10 are still below 70% accuracy for epsilon =1 (which is often considered an acceptable privacy risk).

While the study is fairly interesting, I'm not sure if the technical contribution is enough

• Prior to our work, very little research has explored alternative differential privacy techniques for private machine learning. One notable exception is the Cactus mechanism (https://arxiv.org/abs/2207.00420), however, it is not implementable for models with a large number of parameters (>40). As far as we are aware, no work exists even considering Laplace noise for DP-SGD. Yes, our work finds that the Gaussian mechanism is close-to-optimal for the family of privacy mechanisms we explore. However, we emphasize our other contributions:
  • We provide the first exploration of DP mechanisms outside of the Gaussian Mechanism for DPSGD for private ML and provide a practical implementation of this mechanism for private ML.
  • We provide a framework for comparing Laplace and Gaussian mechanisms, as well as how to use existing privacy accountants for arbitrary mechanisms.
  • To us, the authors, it is exceedingly surprising that the Gaussian Mechanism performs close to optimally. It’s hard to apply a historical rationale for why previous researchers only considered the Gaussian mechanism, but it seems likely that this is because they were familiar with it mathematically, and it has nice properties for computing integrals. However, neither of those two reasons are any reason why the Gaussian mechanism (out of the infinitely many other possible mechanisms) should perform optimally. As a field, we have explored very little of the space of potential DP mechanisms, and to find that one of the two original mechanisms were in fact near optimal, is at the very least surprising.
  • In our exploration we provide a mostly negative result, that researchers should mostly not explore other unimodal DP mechanisms for DPSGD. While positive results are easier to accept, a negative result (that Gaussian noise performs near-optimally) is nonetheless a significant step forward in our understanding of privacy-accuracy tradeoffs in machine learning.

Regarding your questions - yes, we believe you are correct, and we have updated it accordingly. As you noted, we also find that this does not change the argument.

Thank you very much for your time and comments.

We thank the reviewer for the thorough comments and the kind words. We address the weaknesses stated in the review below:

• Regarding the state-of-the-art results: as you stated, achieving state-of-the-art was not the primary goal of the work, and rather only a baseline to compare against; given this goal, we found that 3 runs were sufficient because the resulting standard deviations in nearly every case was less than 0.3%.
• We agree that this is one more hyperparameter to tune, and generally agree that “I see the main contribution of this work is showing that the beta doesn't have too much effect rather than improving the accuracy of current mechanisms.” We also agree, as you state, that “there are so many hyperparameters to tune, so giving practitioners support in using the Gaussian mechanism as a default is useful.”

We have addressed the typos, thank you for pointing those out.

Thank you very much for your time and comments.