Optimizing Noise Distributions for Differential Privacy

We thank the reviewer for their constructive feedback. Below are our responses to their concerns.

The abstract claims "significant[ly]": Since "significant" is subjective, we will clearly specify the gains in the abstract if accepted. We addressed our framework's practicality in our response to reviewer WDdd and kindly refer the reviewer to that discussion (see our responses to all their questions).

Q1) In our framework, $N$ is the number of bins before the geometric tail begins, resulting in a probability vector of length $N+1$. $\Delta$ is the bin width, so the geometric tails start beyond $-N\Delta$ and $+N\Delta$. Figure 4 provides the values of $\Delta, r$, and $N$ for a specific distribution. Our rule of thumb for selecting these parameters is to choose a small $\Delta$ (around 0.05) and set $N$ such that $N \Delta$ is about 20 times the noise’s standard deviation to capture its behavior effectively. For $r$, we select a value close to 1 (e.g., 0.9999) to ensure the noise has a heavy tail, as a light tail may fail to satisfy the pure DP constraint. In Algorithm 3, $T$ refers to the time step for updating $\alpha$. Specifically, every $T$ iterations, $\alpha$ is updated to optimize the moments accountant. Based on our observations, a $T$ between 10 and 20 is sufficient to determine $\alpha$. We set the total number of iterations, $K$, to 5,000, but with preconditioning, convergence typically stabilizes around 2,000 iterations based on our observations. We will include these details in the final version.

Q2) Our method is computationally efficient due to the convexity of the optimization and the use of preconditioned gradient descent, achieving an optimal distribution in 18.7 s ± 431 ms (mean ± std). While our method requires additional computation during the optimization phase compared to Laplace or Gaussian, this is a one-time cost. Once completed, sampling is fast and straightforward due to its discrete nature using inverse CDF. Specifically, for sampling 50,000 times, our noise takes 4.61 ms ± 94.2 µs, as compared to 3.37 ms ± 980 µs for Gaussian (numpy.random.normal) and 3.2 ms ± 877 µs for Laplace (numpy.random.laplace). All runtime experiments were conducted on Google Colab's CPU environment without GPU acceleration. If accepted, we will include more detailed runtime comparisons.

Q3) The Staircase mechanism is optimal in the single composition setting for pure DP ($\delta = 0$). Since we did not consider the $\delta = 0$ case in our experiments, we compared our noise to Laplace instead. If accepted, we will compute the composed $(\epsilon, \delta)$ values for Staircase, compare them with our noise, and add figures showing how our distributions recover this mechanism. We have addressed why our framework can recover the Staircase in our response to reviewer TUrb (Q2 and Q3) and kindly ask the reviewer to refer to that rebuttal for more details.

Q4) Since Gaussian is a straightforward baseline, our algorithm starts from a Gaussian approximation to ensure the initial point is feasible. The main challenge is preventing noise parameters $(p_0, \dots, p_N)$ from approaching zero, as Renyi DP requires full support to avoid instability. This leads to slow convergence since it requires careful steps to stay within the positive orthant. To address this, we introduced a novel preconditioning approach in Section 4 (end of page 7, start of page 8) to stabilize the objective, prevent numerical issues, and accelerate convergence. As a result, we do not encounter overflow or underflow issues. In particular, the iterates on the optimization variable stay feasible while continually improving the objective, after starting from a point close to the Gaussian as mentioned above. This ensures that, even if the algorithm does not fully converge (which empirically it almost always does), it will achieve a good solution. We hope this addresses the reviewer's concern. If not, we would appreciate further clarification.

Q5) We appreciate this query. Our distribution is setting-dependent and adapts to approach the optimal shape in each regime. The existence of fundamentally different optimal distributions, such as the monotone Staircase and non-monotone Cactus, highlights the difficulty of assessing a noise distribution’s utility-privacy tradeoff based solely on its appearance. Supporting both types demonstrates our framework’s generality and optimality. The shape of our optimal distribution combines the characteristics of different distributions depending on the setting. Figure 2 implicitly illustrates how the shape of our optimal distribution transitions between Laplace and Gaussian as cost or composition increases; specifically, our distribution resembles Laplace when Laplace is close to optimal; similarly for Gaussian. We already included an example of an optimized distribution in Figure 4. We will add more illustrations of optimal distributions in the final version.

We appreciate the reviewer's thoughtful feedback. Below, we provide detailed responses to their concerns.

From the numerical results presented in the figures, it appears that there is little difference for smaller values of ϵ (e.g., ϵ<2) compared to the Gaussian distribution. Meanwhile, adding Gaussian noise may be more straightforward for statistical inference or uncertainty quantification (for example, when constructing confidence intervals). Could the authors provide further justification for adopting the proposed distribution instead?

We appreciate the reviewer’s careful consideration of our work. If the reviewer is referring to Figure 3 in our paper, where there is a small difference for $\epsilon<2$ , we agree with the reviewer regarding this specific plot. However, we would like to highlight that the results in this plot are sensitive to the cost threshold ($\sigma^2$) and the number of compositions. In certain settings, our noise mechanism can achieve an improvement over Gaussian noise even for $\epsilon$ values less than 2. For example, if we compare our optimized noise, designed for 10 compositions and $\delta = 10^{-6}$, against Gaussian and Laplace distributions, all with the same standard deviation of 8, at the target $\delta = 10^{-6}$, our noise achieves an $\epsilon$ of 1.62, compared to 1.76 for Laplace and 1.74 for Gaussian noise. Replacing the Gaussian or Laplace distributions with our optimized noise yields improvements of 6.89% and 7.95%, respectively, in the $\epsilon$ value. So, in general, it is not true that Gaussian noise should always be preferred for $\epsilon$ values less than 2.

From the perspective of sampling complexity, we note that classical inverse CDF sampling methods can be applied straightforwardly to our optimal noise distribution. Thus, while our optimal noise distribution provides a better privacy-utility tradeoff than Gaussian noise in appropriate settings, its practical use remains efficient. We have included sampling time comparisons between our noise and Gaussian in the rebuttal for reviewer zWjf (response to Q2) and kindly encourage the reviewer to refer to that for further details.

We have provided additional justification for why our noise should be adopted in the rebuttal for Reviewer WDdd, and we kindly ask the reviewer to refer to that section for more details (please see our responses to all questions from that reviewer).

It might be more illustrative if the authors included an example to demonstrate the advantages of their method. For instance, it would be helpful to see a specific problem where the variance of the new privacy-preserving estimator is clearly lower than that of a traditional estimator.

We thank the reviewer for this insightful comment. In our rebuttal to reviewer WDdd, we have provided details on the practicality of our framework, including applicable datasets (response to Q2) and an example illustrating how our method reduces estimator variance (response to Q3). We kindly ask the reviewer to refer to that rebuttal for further clarification.

We would like to thank the reviewer for acknowledging the novelty of our work and its mathematical contributions. Our responses to the concerns are provided below.

Q1) In the preliminaries (line 120-130), the definition of $\sim$ is duplicated ( for probability distribution and for the neighboring sets). After Eq. (11), the authors need to explain the constraint with an example (if $c(x)=x^2$, the constraint limits the variance of additive noise).

We appreciate the reviewer for pointing out the duplication in the preliminaries and the need for further clarification on the constraint after Eq. (11). We will include an example to clarify the constraint and address the duplication in the final version of the paper.

Q2) In the contribution parts, the authors mentioned that “the algorithm recovers as special cases noise distributions that are known to be optimal in different regimes, such as the Staircase and Cactus mechanisms.” However, the reviewer cannot find the related experimental results.

We thank the reviewer for their valuable feedback. Our distribution class is rich enough that it can closely approximate either the Staircase mechanism or the Cactus mechanism. Thus, by the nature of the optimization problem, our resulting distribution will always be at least as good as either mechanism. Specifically, the Cactus mechanism (which is optimal when the number of compositions tends to infinity) is derived by minimizing the KL-divergence, which corresponds to the limiting case of Renyi DP (RDP) as $\alpha$ approaches 1. On the other hand, the RDP of order $\alpha=\infty$ is exactly pure DP, and our optimization will yield the Staircase mechanism as the optimal noise distribution.

As we explained in the introduction, the optimal $\alpha$ value, chosen through the moments accountant formula (used in our algorithm), is closely linked to the number of compositions. This method effectively determines a large $\alpha$ for a single composition with $\delta$ of 0 (pure DP), and an $\alpha$ close to 1 for larger composition scenarios, leading to the Staircase and Cactus distributions as special cases. In the final version, we will include additional figures comparing the noise distributions derived from the settings optimal for Staircase and Cactus, and show how our approach recovers these distributions.

Q3) In the numerical results, the authors said “a small number of compositions, Laplace is close to the optimal, and the Gaussian is close to the optimal if large number of compositions,” although the optimal one would be star-case and cactus distributions. Can the authors provide experimental results by adding two baselines (stair-case and cactus).

We appreciate the reviewer’s suggestion to compare against these baselines. While we did not include them in the current experimental results (as our plots primarily focused on settings with a non-zero $\delta$ and moderate composition, where Gaussian and Laplace noise were the better choices and Staircase and Cactus were not optimal), we will include detailed plots in the final version to compare the noise obtained from our method with the Staircase and Cactus baselines.

Q4, Q5) Are there any additional practical examples regarding moderate composition regimes other than U.S. Census Bureau? Please better introduce the relation between the authors’ work and the machine learning. For example, how can we use moderate competition in Machine Learning field?

We discussed potential datasets for moderate composition regimes in the rebuttal to Reviewer WDdd (Response to Q2) and provided an example in Response to Q3, demonstrating the improvement on a real-world dataset when using our noise. Due to space constraints, we kindly ask the reviewer to refer to those sections.

We first would like to thank the reviewer for recognizing the novelty of our work and for their constructive comments. Below, we provide a detailed response to their concerns.

Q1) The main issue is that the experiments do not convey the power of the proposed approach and except for very narrow regimes, it would be okay to use the Gaussian or the Laplacian setting directly.

We appreciate the reviewer's comment. While Gaussian noise is provably optimal only in the asymptotic setting as sensitivity approaches zero, no such proof exists for Laplace noise in general. Our framework allows us to compute the optimal noise distribution for any setting, and by comparing $(\epsilon, \delta)$ guarantees, we can now see that Gaussian and Laplace noise are near-optimal in certain cases. This insight is a direct outcome of our approach. It should be emphasized that, without our approach, it is not clear when it is best to choose Gaussian versus Laplace. Rather than replacing Gaussian or Laplace noise universally, our method provides a principled way to determine when to use them versus our optimized distribution. Figure 2 comprises a handy guide that tells a practitioner exactly what to do based on their setting.

In the moderate composition regime, highlighted in Figure 2, the improvement achieved by our approach compared to classical distributions is nontrivial. For example, Figure 1 illustrates a setting in which our approach improves the epsilon value by more than 5%. For those on a tight privacy budget, this is significant.

Q2) The experimental setting is pretty limited and it would be nicer to see further results on ML/DL models referenced in the introduction which would have a substantial number of compositions beyond 10 that are shown here.

While modern ML often focuses on high-dimensional datasets, where training with DP guarantees requires a high number of compositions, developing predictive algorithms for tabular datasets has always been, and continues to be, a key part of the ML repertoire. In particular, sharing statistics for a restricted number of compositions in a private manner is a key application of DP.

Some tabular datasets come with predefined SQL queries or are used in environments where a limited number of queries is the norm. For example, the U.S. Census Bureau enforces pre-approved aggregate queries to safeguard sensitive data. Similarly, health datasets like NHANES and the Medical Cost Personal Dataset restrict researchers to approved statistical queries, such as calculating the average medical charges for specific age groups. These constraints highlight that in many real-world scenarios, a small number of queries (e.g., 10-20) is both standard and necessary, reinforcing the practical value of optimized noise mechanisms tailored for such settings.

Q3 ) How do you think this framework would apply to real-world applications? Will there be substantial gains over Gaussian or Laplacian distributions?

As mentioned above, there are many practical datasets for which a small number of compositions is meaningful. To demonstrate the superior performance of our noise mechanism, we have an additional experiment that we performed for this review; it involves 10 queries on the Medical Cost Personal Dataset. These queries include calculating the average medical charges for specific age groups, total charges by smoker status, average BMI by region, and other similar aggregate statistics. We target the $(\epsilon, \delta) = (2.83, 10^{−6})$ setting. As illustrated in Figure 1 of our paper, Laplace noise achieves this with a standard deviation of 5, outperforming Gaussian noise. To achieve the same $\epsilon$ of 2.83, our noise mechanism requires a lower standard deviation of 4.73. To highlight the utility of our mechanism for the abovementioned dataset, we use the metric of MMSE (minimum mean squared error) as follows: we compute the empirical average (over 10 queries, repeated 100k times) of the squared difference of the true query and the clipped+noisy DP query output. The resulting average MMSE for Laplace noise is 24.98, while our optimized noise achieves an MMSE of 22.37, resulting in a 10.4% improvement.

If accepted, we will include these results in the final paper. We hope this example highlights the value of our work and its practical advantages in real-world machine learning applications.