Optimizing Noise Distributions for Differential Privacy
Authors: Atefeh Gilani
Juan Felipe Gomez
Shahab Asoodeh
Flavio Calmon
Oliver Kosut
Lalitha Sankar
Venue: ICML 2025 poster (2025)
Keywords: Differential Privacy
Renyi Differential Privacy
Optimization
Primary area: social_aspects->privacy

Abstract: We propose a unified optimization framework for designing continuous and discrete noise distributions that ensure differential privacy (DP) by minimizing Rényi DP, a variant of DP, under a cost constraint. Rényi DP has the advantage that by considering different values of the Rényi parameter $\alpha$, we can tailor our optimization for any number of compositions. To solve the optimization problem, we reduce it to a finite-dimensional convex formulation and perform preconditioned gradient descent. The resulting noise distributions are then compared to their Gaussian and Laplace counterparts. Numerical results demonstrate that our optimized distributions are consistently better, with significant improvements in $(\varepsilon, \delta)$-DP guarantees in the moderate composition regimes, compared to Gaussian and Laplace distributions with the same variance.

Optimizing Noise Distributions for Differential Privacy
Atefeh Gilani
Juan Felipe Gomez 2 Shahab Asoodeh
Flavio P. Calmon
Oliver Kosut Lalitha Sankar'
Abstract
(Abowd et al., 2022) publishes demographic statistics such population density or employment rates for each state, re- quiring repeated applications of privacy- seaeypppesn methods. On the other hand, the large composition regime involves thousands of sequential applications of privacy mechanisms, such as during the training of a machine learning model.
We propose unified optimization framework for designing continuous and discrete noise distri- butions that ensure differential privacy (DP) by minimizing Rényi DP, variant of DP, under a cost constraint. Rényi DP has the advantage that by considering different values of the Rényi pa- rameter a, we can tailor our optimization for any number of compositions. To solve the optimiza- tion problem, we reduce a finite-dimeniioall convex formulation and perform preconditioned gradient descent. The resulting noise distributions are then compared to their Gaussian and Laplace counterparts. Numerical results demonstrate that our optimized distributions are consistently bet- ter, with significant improvements in (c, 6DD guarantees in the moderate composition regimes, compared to Gaussian and Laplace distributions with the same variance.
The most widely used noise distributions incorporated into privacy mechanisms for achieving DP are Laplace noise (Dwork et al., 2006b), typically employed when pure DP is desired, and Gaussian noise (Abadi et al., 2016), often used for approximate DP (i.e., (c, 8)-DP). However, these distri- butions may not necessarily be optimal across all settings in which they are applied. For example, while the Gaussian distribution is commonly used to ensure approximate DP in the large composition regime, the parametrized Cactus distribution has been shown to be optimal in this regime for fixed sensitivity >> 0 (Alghamdi et al., 2022). Moreover, the Schrödinger distribution has been demonstrated to be optimal for vanishing sensitivity (s + 0+), and it only re- covers the Gaussian distribution as a special case under a quadratic cost function (Alghamdi et al., 2023). Addition- ally, in (Geng al., 2015), was shown that the Staircase distribution is optimal for E-DP in the single composition regime. In this paper, we focus on designing optimal noise distributions tailored to fixed number of compositions and sensitivity. We demonstrate that the resulting optimal Rényi DP noise distribution significantly outperforms both Laplace and Gaussian distributions in the moderate compo- sition regime.
1. Introduction
Differential privacy (DP) (Dwork et al., 2006a;b) provides strong privacy protections by ensuring that information re- leased from queries on sensitive data does not reveal whether any individual is included in the dataset. This is achieved through privacy mechanisms that add noise to query re- sponses, effectively masking any private information.
In practice, privacy mechanisms are rarely applied only once to sensitive data. Instead, they are often used sequen- tially, with the frequency depending on the specific use case. In what we call the moderate composition regime, privacy mechanisms are applied limited number of times re- lease aggregated data. For example, the U.S. Census Bureau
Discrete noise distributions also hold significant value for DP. This is because finite precision implementations that generate continuous random variables can result in naive floating-point approximations which have been shown to compromise their de facto privacy guarantees (Mironov, 2012). Restricting noise distributions to integer support offers resilience against doating-poin attacks and better suits applications involving integer-valued queries, such as population counts in the US Census. To address these chal- lenges, the discrete Gaussian distribution (Canonne et al., 2020) and the discrete Laplace distribution (Ghosh et al., 2012; Balcer & Vadhan, 2017) have been proposed. These distributions, supported on integer values, serve as natural discrete analogues the continuous Gaussian and Laplace distributions.
SShoool of Electrical, Computer and Energy Engineering, Ari- zona State University, Tempe, AZ, USA 'Department of Physies, Harvard University, Cambridge, MA, USA 'Department of Com- puting and Software, McMaster University, Hamilton, Ontario, Canada "School of Engineering and Applied Sciences, Harvard University, Cambridge, MA, USA. Correspondence to: Atefeh Gilani <agilani2 @ asu.edu>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Optimizing Noise Distributions for Differential Privacy
In this paper, we apply exactly the same approach as for continuous distributions optimize discrete noise distribu- tions. The comparison between the discrete Rényi DP noise distribution and the discrete Gaussian and Laplace distribu- tions mirrors that of their continuous counterparts, with the discrete Rényi DP noise distribution also outperforming the discrete Gaussian and Laplace distributions the moderate composition regime.
Algorithm Optimal Noise Distribution for (s, 6)
input Privacy parameter 6, Number of compositions Ne.
Noise scale a, Query sensitivity 8, type (Discrete or Continuous), Hyperparameters
output Optimal distribution P minimizing e for the
given ō and N₂. satisfying E[Cost] S o²
1: Po IniitalzeDDitrrrbutooottspe (yyp
2: P + OptimizzationAlgorrttttt/ZZ Po, type, o, No:
Whether in the continuous or discrete case, optimizing with respect to (e, -DP in the context of compositions is chal- lenging due to the problem's non-convex nature. To over- come this, we leverage the properties of Rényi differential privacy (RDP) (Mironov, 2017), a variant of DP defined in terms of the Rényi divergence of order a, where a E (1, 00). RDP has garnered significant attention (Abadi et al., 2016; Chen et al., 2019; Feldman et al., 2021; Lécuyer et al., 2021; Feldman et al., 2022). One of its key advantages is that, for composition, the total RDP is the sum of the individual RDPs. Therefore, our approach is to optimize each RDP term individually, which is sufficient to optimize the overall privacy guarantee. In addition, RDP can be converted into (e, 0)-P, as in the moments accountant in (Abadi et al., 2016; Mironov, 2017: Bun & Steinke, 2016; Balle al., 2020; Asoodeh et al., 2021). This conversion involves min- imizing over the Rényi order a. Thus, the optimal a is closely tied to the number of compositions, and is generally decreasing with the number of compositions: tends toward I in the large composition regime, and towards infinity in the single-comp compositin regime. For moderate compositions, generally lies within an intermediate range, avoiding the extremes of I and infinity.
RDP noise
10
Staircase
Cattus
Gaussian
10-1
Laplace
d= 10
10-1
10
10-1
10-4
10-1
10
0.0
0.5
E
Figure 1. This plot compares the privacy curve of our opti- mized noise-designed for 10 compositions, s = 1. and å = 10 10-6_ a-aainst other noise distributions, all with the same standard deviation of 8. At the target 8 = 10 our noise achieves an of 1.62, compared 1.76 for Laplace/Staircase and 1.74 for Gaussian/Cactus Replacing these mechanisms with our optimized noise results in at least 6. 6.89% improvement in the e value
Because our framework allows us to optimize the noise for any a, our approach encompasses optimal noise distribu- tions in both the large and small composition regimes. In the large composition regime, the Cactus distribution is shown to be optimal in (Alghamdi et al., 2022); this distribution is found by minimizing the Kullback-Leible divergence, which corresponds to RDP as 1. Since we incorporate the moments accountant into our optimization framework, for large numbers of compositions, we will automatically seek a near 1, thus recovering the Cactus distribution. In the single-composition regime for pure DP, the optimal a tends to infinity, and our noise distribution recovers the Staircase distribution, consistent with RDP converging to pure DP as
squared-error (MSE). The algorithm outputs an optimized discrete or continuous additive noise distribution. Figure I illustrates the resulting (e, 8) curve for an optimized noise distribution considering 10 compositions, noise standard deviation constraint of 8, and target å 10-6 Relative to other noise mechanisms, our optimized mechanisms achieve lower for the same distortion at the target 5.
2. We formulate a finite-dimensional convex optimization problem for producing optimized noise distributions and solve using preconditioned gradient descent, denoted as OptimizaaiionAllorilln in Algorithm 1. This convex prob- lem leverages RDP of order as an intermediate optimiza- tion objective. The RDP hyperparameter is automatically selected based on the the user-defined input parameters.
Our main contributions include:
3. Our algorithm recovers as special cases noise distribu- tions that are known to be optimal in different regimes, such as the the Staircase and Cactus mechanisms. In the mod- erate composition regime (roughly 10-40 compositions), both discrete and continuous distributions derived from our framework achieve superior (s, 6)P guarantees compared to their Gaussian and Laplace counterparts for target cost,
1. We propose an algorithm for optimizing noise distri- butions under (c, 6DDP, outlined in Algorithm 1 I. Our procedure receives as input user-defined (i) target 8, (ii) number of compositions, (iii) sensitivity, and (iv) average distortion per query (i.e., a cost constraint) such mean
'Our implementation is available on GitHub (git, 2025).
2

---

Optimizing Noise Distributions for Differential Privacy
number of compositions, and 8. We validate the favor- able performance of our optimized noise distributions using Connect-the-Dots (Doroshenko et al., 2022) accounting.
The above is non-adaptive composition, in that each mecha- nism works independently of the other's output. In contrast, in an adaptive composition, the second mechanism may depend on the output of the first. A similar composition result holds for the adaptive setting (Mironov, 2017), but for brevity we omit the details. A particular consequence of Proposition 2.3 is that, if the same (or equivalent) mech- anisms are composed Ne times, then the RDP simply multiplied by Ne-
2. Preliminaries
Notation. Vectors are represented by bold lowercase letters, e.g., x. and matrices by bold capital letters, e.g., A. The symbol B denotes the Phoore-Penrose right inverse of B (Wikipedia, a). The notation diag(x) x) denotes diagonal ma- trix with the elements of x. The symbol [N] denotes the set of integers from 0 to N, i.c., [M] = 2,...... J.. The symbol c represents the cumulative distribution function of the standard normal distribution.
The moments accountant (Abadi et al., 2016) provides a method to derive (e, 8) guarantees from (a, 7) guarantees. The most basic form of the moments accountant follows. Proposition 2.4. (Abadi et al., 2016) For mechanism M,
We review some basic definitions and results from the DP literature. Given an alphabet X, let P(X) be the set of distributions supported on X. For P. Q P(X), the Rényi divergence of order o, for E 10, (1, io),
(Ø) S inf Tm(() + log(1/6) as
--
While improvements to the moments accountant have been made in (Balle et al., 2020; Asoodeh et al., 2021), we use this simple version in our algorithm to simultancously op- timize for the noise distribution and a. However, when we perform numerical privacy accounting for the resulting distribution, we use the state-of-the-ar Connect-the-Doo accountant.
1
P(X) Q(X)
a-1
log Ep Qa(l)))== a
(1)
Let 2 be a set of possible datasets, and ~ be a "neighboring" relation among elements of D. That is, for d, d' E D we write d ~ d' to mean that d and d' are neighbors, which typically means that they differ in one entry. A mechanism function M : D + P(X), which, for each d D, selects distribution Ma E P(2'). This can be interpreted as conditional distribution for a random variable supported in X' given a dataset from 'D. Definition 2.1. (Dwork et al., 2006a;b) A mechanism M: D + P( is said to be (c. DDD if for all A C X,
The sensitivity of query q : D - TR describes the max- imum difference in the query's output when changing a single entry in the input dataset. Formally, it is defined
max d,d' dDd
la(d) - q(d")).
(8)
Given a real-valued query function & with sensitivity bound s, the Gaussian mechanism involves adding Gaussian noise with zero mean and variance 8² to the query g. Similarly, the Laplace mechanism involves adding noise from Laplace distribution with zero mean and scale parameter & to the query q.
Ma(A) S e Ma (A) + 5 for all d, d' E D, d
(2)
For a mechanism M, we also define the best e for a given as (6) = inf .M ().)).
Definition 2.2. (Mironov, 2017) A mechanism M: P(X) is said to be (a, (a.P))
For many natural queries, the output is inherently discrete, specifically integer-valued, such as when counting how many records in a dataset meet a certain condition. In these cases, preferable to add discrete noise directly to the query results. Adding continuous noise to discrete results would require rounding, which can affect the privacy guar- antees. Discrete Gaussian and discrete Laplace distributions are the discrete counterparts of their continuous versions and are specifically designed for discrete- queries. The definitions of discrete Gaussian and Laplace distributions are as follows. Let Z be the set of integers. The discrete Gaussian distribution, denoted Nz(u, o²), for μ Z and (5)
Da(MalllMa) I y for all d, d' E D, d d'.
(3)
For mechanism M, also define the best for given as
(m = inf(y: : M is (a, RDP).
(4)
For two mechanisms M _M each outputting a vari- able in X, their composition M: 'D - P(X x X') is
Ma(ai, = (M) (Iz).
> 0, is the PMF in P(Z) given by
Proposition 2.3. (Mironov, 2017) For any mechanisms M (2) and their composition M,
20
P(x) =
1 E Z.
(9)
(u-waa 20
(a) S 7Maa (a) + (a).
(6)
Σ
yEZ e
3

---

Optimizing Noise Distributions for Differential Privacy
approximate solutions (11) while being computationally tractable. These families draw inspiration from simi- lar finite-dimensional parameterization in (Alghamdi et al., 2022). We then present a method for solving the optimiza- tion problem within these defined families.
The discrete Laplace distribution, denoted (a, t), for E E and t > 0, is the PMF in PZ)) given by
ellt -1 c-1z-ul/t JEZ. P(x)=
el + E
(10)
For the continuous case, we focus on symmetric piecewise constant probability density functions (PDFs). Importantly, this approach is highly flexible, as any PDF can be closely approximated by using sufficiently small bin widths. This shifts the problem from optimizing the density at every real number to determining the probability p. of bin i. Given these probabilities, the PDF is given by
3. Optimized Rényi DP Distributions
In this section, we find noise distributions with the best Rényi DP guarantees by formulating a minimax optimiza- tion problem. To set up this problem, we first give the following definitions. We use Z to denote the domain of the DP query output, which can be either the real numbers or the integers. The set S is defined as the intersection of the interval [-s, s] with Z, where s E Zz represents the query's sensitivity. Specifically, S [-s, s]] if 2 I,, and S = (-s...... O......) $} if Z = Z. We assume a cost function : 2 - [0, 0o) that is symmetric, and an upper bound C E R+ on the expected cost. For a function f.Tef the shifted version of by t, i... (T) = f(z t)..
[(z) = Piil for 2 E 4, iE
(14)
A
where 4, = ( (i+ (i, 444 denotes the open interval corresponding to bin i, and A > 0 represents the bin width, Remark 3.2. As the Lebesgue measure of the breakpoints in the piecewise-constanl representation is zero, it is not necessary explicitly define the value of f at these points.
This formulation still involves countably infinite variables, specifically {piliezo. To ensure a finite number of vari- ables, we introduce the constraint that the distribution ex- hibits geometric tails. The geometric tails begin beyond a specific interval, starting after bin N, where N is a hyper- parameter for the distribution family. The decay rate of the geometric tail is given by a second hyperparameter r. Impor- tantly, this tail assumption does not significantly impact the optimization, provided that the interval is sufficiently large to capture the majority of the PDF's significant behavior. For fixed A, these tails are fully characterized by the prob- ability mass of the bins immediately preceding them and the decay factor r. This reduces the problem to determining the probability masses of the bins preceding the geometric tails, thus converting the problem into a cimte-dimensional one. The following formally defines the family of distributions under consideration.
With the above definitions, the optimization problem is
minimize max Da (PZ))TP2) PZEP(Z) IES subject to [
(11)
For a >> 1, we can move the min-max operation inside the logarithm of the Rényi divergence, considering it as our main objective. Let 9o (Pz, I) denote the expression inside the logarithm of D& (Pz P2])
). defined as:
Pz
ga (2., 1) = Epz
(12)
TzPz
,
and let 9a (P2) denote the inner maximization:
ga (Pz)
max Ia (P.,t).
(13)
1ES
We first show that gr. g.. (Pz) is convex in Pz. By leveraging this property, along with the symmetry of the cost function, we restrict our search to symmetric noise distributions, as formalized in the following theorem. A detailed proof is provided in the Appendix A.
Definition 3.3 (Symmetric Piecewise- Constttt PDF Fam- ily). Let N E N, r E (0. 1), and A > 0. The PDF associ- ated with vector of probabilities p = (Po. Pi.... .PN) E [o, 1 is
PR] A
if 2 E I, |0| < N,
Theorem 3.1. The function ga (Pz) is convex in Pz. More- over, it suffices to restrict the search to the set of symmetric noise distributions within P(Z) to solve the optimization problem in (11).
Sp..N,((=)==
=
(15)
PN
I-N,
ff 10 2 N,
A
subject to the normalization constraint
3.1.
Distribution Classes
[DDnNaat)) dz Po + Σ P3
N-1
2pN 1 1-r
1. (16)
While we would like to solve (11), it cannot be solved as-is because the search space of distributions is infinite- dimensional. In this subsection, we address this by defining finiteddimensionll families of distributions that can closely
For the discrete case, it is again sufficient to restrict our search to symmetric distributions. We also assume geomet-
4

---

Optimizing Noise Distributions for Differential Privacy
ric tails as in the continuous setting reduce to a finite- dimensional search space. The following gives the family of discrete distributions under consideration.
Je (P,, () in (12) for the two distribution families, and de- lineates the feasible regions for both continuous and discrete cases. Notably, the resulting finite-dimensional convex opti- mization problem is almost the same for the two domains.
Definition 3.4 (Symmetric PMF Family). Let N E E (0. 1). The PMF associated with a vector of probabilities = (Po.PI.". .. :PN) E [0,1]*+ is
Theorem 3.6. Let 8 be the sensitivity of a query. Within the symmetric piecewise-conse constant PDF family defined in s Definition 3.3, with a specified bin width of A such that A is an integer, the optimization problem for the continuous case, as detailed in (11), can be reformulated as follows:
PhI PNNIllNN, for i E Z, with | > N, (17)
for E Z, with |i| S N
(i)r,(((==
subject to the normalization constraint:
minimize p= (po-P1 .PN)
max
9a (p.t)
KE(1 LL...,
N
2PN +
subject to
[[((Z)) S C,
E
Pp....(0) = Po + iEZ
pt
1. (18)
--r
N-1
Po + 2
Σ
Pj +
2 PN
= 1,
1-r
The following proposition characterizes the expected cost for these two distribution families.
/=1
ps E [0, 1]
for all iE [NV,
(22)
Proposition 3.5. Let Z be a random variable with distribu- tion given by either the continuous or discrete distribution families described above. Then the expected cost is
where
N-1
ga(p,t) 1 --
PN P ( (n(l-o)t + trar)
+ Σ
Pitt1 Pla
N-1 P.A, + 2pN im N
E[c(Z)] Ao +
Σ i=1
NN Ai, (19)
+ (
Σ
ras
p(51"
1-a
j=N-(+1
for a continuous distribution,
-N-1
+ PN 1-a 1laa-N(1-0)
Σ j=-t-N
Pit+si r -11--)) (23)
A; = A - d(=) dz, Vi E Z2o, =EI,
(20)
For the discrete case within the symmetric PMF family from Definition 3.4, the optimization problem in (11) can also be reformulated as (23) except that we take A = 1. The cost constraint [[c(Z)] S for both cases is further detailed in Proposition 3.5.
and for a discrete distribution A; = d(i). In the special case where c(z) = 22, corresponding to the variance? of Z,
the expression simplifies to. for the continuous case,
2
N
Var ()
12
+
24
2
P 2
Proof Sketch: The objective in (22) is the quantity inside the logarithm of the Rényi divergence - thus the RDP can be easily calculated from the optimal objective. Although the inner maximization in the continuous case initially con- siders t E [-s, s). we demonstrate that the divergence is maximized when the bins of a piecewise constant PDF align with those of its shifted version. In this scenario, the opti- mal shift is multiple of the bin width A within the interval [-s The set (1..... A corresponds to the possible in- teger multiples of A that determine the optimal shift values. The detailed proof is in Appendix C.
1=1
2 T2 - 1)² + (2 - 2r) + r(2N + +1)
+ 2pN
12
(1 r3
(21)
For the discrete case, the variance is the same as in (21), except that the 2? /22 term not present, and A 1.
The proof is provided in Appendix B.
3.2.
Convex Optimization
Within the distribution family described in Definition 3.3 or Definition 3.4, the task of finding the optimal distribution in (1)) reduces to determining the vector p = (Po..... .PN). ). Since 9. (Pz). defined in (13), is convex in Pz. it is also convex in p. Therefore, the minimization component of the optimization reduces to a mnite-dimensional convex op- timization problem. The following theorem characterizes
In the piecewise-constant PDF family introduced in Defini- tion 3.3, setting A creates a PDF where each bin has width of I and is centered on the integers, which can be interpreted as PMF over the integers. This leads to the objective for the discrete case being a specific instance of the continuous case when A = 1.
Theorem 3.6 highlights that solving for the optimal noise in the two domains (continuous and discrete) is nearly identical.
The distribution's 's symmetry ensures has a mean of zero.
5

---

Optimizing Noise Distributions for Differential Privacy
Algorithm 2 Initialize Distribution
Algorithm 3 Optimization Algorithm
input Noise scale o, type (discrete or continuous),
input Privacy parameter 6, Number of compositions Ne. Noise scale a. Query sensitivity s, Total number of iterations K, Initial distribution Po- Distribution param- eters N, r. A, Rényi parameter (a) update time step T, type (discrete or continuous)
Query sensitivity s, Distribbtiin parameters N, r, A
output PPo
1: Cmin f- 0
2: Cmax t 20
3: repeat
output FFinal solution Pк
4: Ö f- Ömin + C'ax
1: 4- 2og (1/6) a +1
N.
2
Calculate A, so the linear constraints for cost and normalization are given by Ap=
5: for = 0 to N - do
6: Pt 2 ( + (1//v//////// - ((i-
3: for l 1 to K do
7: end for
PN + (1-r)(1-00 = )
4: t" < arg max 1... . () Ia (Pk-
8:
5: M (Ping(Pk->
9:
Var t variance of the noise associated with and
6:
< M paa (Pk-1,
type using Proposition 3.5
10:
if Var o² then then
7:
B + AM
11:
Omin + Č
8:
B + ("BB")
9: g < g - B-
12:
else
13:
Ómax t Ò
10: 4b + min [V( (.
14:
end if
11:
Pk Pk-1
15:
until Var and x² are sufficiently close
12:
Imin < Yo (px-1,(")
16:
Po
1-- p
13:
for E nTh 4
210 do
a
14:
P M- 1 pro)
15:
9 5 maxe (1,., 11...... . 9a (p.t)
16:
if 9 < Imin then
The objectives differ only in that A must be 1 for the discrete
17:
P& + P end if
case. Morcover, as shown in Proposition 3.5, for quadratic cost, the constraints differ only in that the continuous case
18:
19:
end for
includes an extra constant term A 22/12 whereas discrete does not.
20:
if le is multiple of T then
JP (a) (0.
21:
a
Remark 3.7. Let a represent the standard deviation of the noise. As demonstrated in (Mironov, 2017), for Gaussian and Laplace distributions, the RDP of order a depends solely on the ratio /ss, rather than on a and s individually. In fact, our noise distributions satisfy exactly the same prop- erty. In the optimization problem in (22), for quadratic cost with C' = 2², we can rewrite the cost constraint from (21) as:
22: end if
23: end for
4. Preconditioned Gradient Descent Algorithm
In this section, we present our algorithms for identifying the noise distribution that achieves the best (e, 5D-DP guar- antees. Algorithm 1 is the overall algorithm, which calls Algorithm and then Algorithm 3. The role of Algorithm 2 is to initialize the vector p. which is passed Algorithm 3. This latter algorithm performs preconditioned gradient de- scent to find the optimal noise distribution.
22
1
N-1
+2
Σ
Pt 12
2
12
1=1
IN - 1)2 + N2 - 2r) + +r(2N +1),
2pM
(24)
(1
r)3 r3
Al Algorithm 2 Overview: Since the Gaussian distribution is straightforward baseline, we initialize with an approxi- mation of this distribution. Since our distribution families cannot exactly capture the Gaussian (or discrete Gaussian) distribution, must slightly adjust the parameters to actly match the desired a. In the algorithm, Ć' represents the variance of the Gaussian: based on this, we derive to approximate a Gaussian with variance Ć. However, the resulting distribution will have a slightly different variance, denoted Var. We employ a bisection algorithm find Ć so
Moreover, s appears only in the set over which we maxi- mize. By fixing s/ A to integer, say m. which is feasible because A can be adjusted to maintain the desired ratio, we get A = s/m. Substituting this into (24), it becomes a function of a/s. This implies that the optimization now depends solely on the ratio a /s. Therefore, the RDP of our noise depend solely on the ratio a /ss, similar to the behavior observed for Gaussian and Laplace distributions.
6

---

Optimizing Noise Distributions for Differential Privacy
10a
10P
RDP nol Cactus
RDP noise Staircase
10-1
10
10a3
Noise PDF
Noise PDF
10
10-1
10
10
10-11
10-3
10-13
10
10
-10.0
-7.5
-5.0
-2.5
0.0
2.5
Figure 2. The left plot compares optimized noise distribution and Cactus distribution, both with standard deviation 0.3, under the setting 10-5, & = 1, and 50,000 compositions, corresponding to a = 1.006 (moments accountant), with noise parameters A 0.005, NV 1600, and 0.9999. The right plot compares optimized noise and a Staircase distribution, both with standard deviation I, under the setting 5 10 20 s = 1, and one composition, corresponding to a = 125.01, with noise parameters = 0.01. N 2000, and 0.9999.
10-20,
10a
10a
10 1
10-1
Noise PDF
Noise PDF
10
10a3
10
10
-15
-1.0
-10.0
-75
-5.0
-2.
0.0
5.0
7.5
10.0
Figure 3. The left plot displays the optimized noise distribution for standard deviation of 4, 5 = 10 corresponding to a 5.95 (using the moments accountant). The right plot shows the distribution for a standard deviation of 8 10 10 1. and compositions, corresponding to 11.32. The noise parameters are A = 0.01, 0.9999, and N 8000 for the left plot, and 4000 for right.
6
1, and 20 compositions,
that Var = 22 The bisection method allows us to converge to the desired variance for the initial noise mechanism itera- tively. It does so by iteratively tightening the chosen upper and lower bounds on Ć' until they converge.
o= where a is the standard deviation the noise. The appropriate cost constraint (depending on whether type is discrete or continuous) from Proposition 3.5 is used in each case. The normalization constraint is in (22).
The main task is to solve the op- timization problem described from Theorem 3.6, given by (22). The minimization problem is convex in so gradi- ent descent will convergence to the optimal objective value. Recall that our optimization is a minimax problem. The maximization in (22) only requires iterating over finite set, while preconditioned gradient descent method is used to solve the convex optimization part.
Algorithm 3 Overview:
Optimization for at Algorithm 3 simultaneously optimizes for and Specifically, we optimize according to the moments accountant formula, given by
Ne log ga (p) log(1/6)
(p) a -
(25)
a
where Ia (p) max. (a... 9a (a t). The initial value of a is set to the optimal or for the moments accountant with Gaussian noise (corresponding to the initialization of p to being approximately Gaussian). Using the fact that the RDP of Gaussian noise is sãa in the moments accountant formula, 20²
Explanation of Key Aspects of Algorithm 3:
Linear constraints: The optimization problem involves two linear constraints, corresponding to the cost constraint (which active) and the normalization constraint. These two constraints can be expressed
the optimal for Gaussian is a" = 20g(1188 a +1. N.
matrix equation: Ap b. We focus on the quadratic cost c(2) z² with
Subsequently, every T iterations, a is updated by taking a Newton step to optimize the moments accountant formula.
7

---

Optimizing Noise Distributions for Differential Privacy
Laplace
RDP
5.0
Gaussian
4.5
Stalrcase
4.0
Cactus
3.5
2.0
1.5
1.0
25
Compositions
Figure For fixed 10 6 grid evaluates different combinations of composition count and noise standard deviation (Ø), marking RDP noise as the winner whenever achieves more than a 2% improvement in over the best alternative (among Gaussian, Laplace, Staircase, and Cactus). Even when another distribution is marked as the best, our noise still consistently outperforms others. although by less than 2%.
109
10-1
10-1
10
10a2
10-3
10-3
10
10:5
(pointwise
(sointwise min)
10-9
Staiicase
10-9
Discrete Staircase
Cactus
Discrete Cactus
10
10
Laplace
Discrete Laplace
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
Figure The plots compare the pointwise minimum privacy curves from our optimized noise distributionn- designed composi- tions, sensitivity I, and varying 5-with privacy curves for Gaussian, Laplace, Cactus, and Staircase mechanisms, all with fixed standard deviation of The left plot shows continuous distributions; the right plot shows discrete distributions. All curves are evaluated at 10 compositions.
Standard gradient descent ill-suited to this optimization problem. The reason that the probability vector is constrained to be non-negative, in addition to the normalization and cost constraints. All these constraints by themselves can be handled by projected gradient descent (indeed, this is our approach to dealing with the normal- ization and cost constraints; see below). However, doing so will tend produce p vectors with zeros, which lead to infinite values of the objective in (23). This blowing-up occurs because the Rényi divergence between distributions with different supports is infinite. Thus, it is not enough to keep in the feasible set, it must be kept strictly fea- sible. This can be addressed using standard gradient de- scent by reducing the step size, but this causes very slow convergence. To address this limitation, we instead use preconditioned gradient descent, where we apply a linear transformation to the solution space, and take gradient step in the transformed space. In particular, we use the
Preconditioning:
transformation matrix M diag(Px-1)-1 where Pk-1 is the current optimization variable. This transformation introduces uniformity, ensuring that p maintains roughly consistent distance from the boundary imposed by the non- negativity constraint.
Gradient Calculation and Projection: After computing the gradient in the transformed basis, we project onto the region that meets the cost and normalization constraints. Satisfying the equation Ap b for vector p in the orig- inal basis is equivalent to satisfying AM- b for vector in the transformed basis.
Backtracking Line Search: The current position Ps-1 1 in the original basis maps to Mp diag(Px-1)
in the transformed basis. Thus, in each update within the transformed basis, the current position represented by all-ones vector. The update rule is: q 1 proj, where is the learning rate. The
P -
8

---

Optimizing Noise Distributions for Differential Privacy
Table I. MSE improvement (%) of RDP noise over Gaussian for å = 10-6 and 10 queries (mean + std across 20 seeds).
Dataset
8 0.62
0.69
0.78
0.84
0.97
1.05
Breast Cancer
8.28
9.14110.19
9.63.10.23
8.6110.17
10.34.10.00
11.48:10.18
Diabetes
8.11=0.19
9.06:10.21
9.4310.16
8.48:1.17
10.06:0.17
11.12::0.22
UCI Heart Discase
8.14
9.05=0016
9.50+0.26
8.52
10.20=0.20
11.31=0.118
corresponding update in the original basis is: Pa M-'q. q.
some of which are shown in Appendix D.
The constraint P 2 0 implies q 2 0, leading to the upper bound 11th = min [M). "
In the two parts of Figure 5, we fix the number of compo- sitions and standard deviation while optimizing the noise distribution for different ō values, for both continuous (left) and discrete (right) domains. Each results in a different op- timized noise distribution, generating its own privacy curve. The RDP noise curves represent the pointwise minimum of these curves: that is, each point (e,6) on this curve is derived from the noise distribution optimized for that spe- cific 5. In contrast, Figure I shows the privacy curve for a specific noise distribution optimized for single target 5. Our approach remains optimal across all 5 values, closely matching the performance of other noise mechanisms in their respective optimal regimes while significantly outper- forming them elsewhere. Note that the range of where we observe the greatest improvement varies with the choice of a and the number of compositions. We provide an additional set of plots for a different combination in Appendix D.
We implement a backtracking line search strategy that evalu- ates learning rates the sequence 10th n1th /2. /210. Among these, the learning rate that achieves the largest reduction in the objective function selected.
5. Numerical Results
In this section, we present numerical results evaluating the privacy characteristies of our proposed RDP noise. All (c, 6)DD guarantees presented here are computed using the Connect-the-Dors accounting (Doroshenko et al., 2022).
Figures 2 and show optimized RDP noise distributions across different settings. In particular, Figure 2 highlights how our framework automatically recovers Cactus and Stair- case distributions in the regimes where they perform best (a close to 1 and respectively).
In Table 1, we report the performance improvement of our optimized noise over the Gaussian baseline on three widely used datasets for prreecy-pess machine learn- ing: Breast Cancer Wisconsin (Diagnostic) (Wolberg et al., 1993), Diabetes (learn developers), and the UCI Heart Dis- ease dataset (Cleveland subset) (Janosi et al., 1988). Details about the datasets and the experimental setup are provided in Appendix D due to space constraints. Since Gaussian noise consistently outperformed Laplace, Cactus, and Stair- case mechanisms across all tested settings (with = 10-6 10 queries, and a range of target & values), we focus our comparison on the Gaussian baseline. As shown, replacing Gaussian noise with our optimized mechanism yields an improvement of 8% to 12% across the evaluated E values.
Figure 4 illustrates what we call the "moderate composition regime," " showing the range of compositions and noise stan- dard deviations (σ) where our optimized noise distribution achieves least a 2% improvement in E compared other known mechanisms (Gaussian, Laplace, Staircase, and Cac- tus) for 8 10-6, The regions with more than two percent improvement depend on both and the number of compo- sitions. Importantly, there is no single mechanism that is always best across all parameter settings-so so finding the best one typically requires testing all four for each combina- tion. Even in cases where another distribution is labeled as the best, our noise still consistently performs better than the rest, although the margin is less than 2%. Our noise is bene- ficial not only when it gives a clear 2% greater advantage, but also in situations where it is unclear in advance which mechanism will perform best. For example, even though the Staircase distribution is provably optimal only for a single composition and in the pure DP limit -> 0), it sometimes outperforms the others 8 10-6 for certain a and compo- sition choices- yet it is easy mistakenly pick different baseline like Laplace. Our optimized noise is robust and helps avoid mistakes when choosing among existing mecha- nisms. Note that this plot is specific to = 10-6; for other values 8, there are additional combinations of a and com- positions where our noise provides similar improvements,
6. Conclusion
We have introduced a unified optimization framework to identify optimal continuous and discrete noise distributions for 8)- for a given cost and number of compositions. To address the problem's 's non-convexity, we have converted the objective into Rényi DP of an optimized order o, yield- ing finite-dimensional convex optimization problem. We have introduced a novel preconditioned gradient descent algorithm to efficiently solve this optimization problem. The resulting noise distributions are consistently better than Gaussian and Laplace distributions, with significant im- provements in the moderate composition regime.

---

Optimizing Noise Distributions for Differential Privacy
Acknowledgements
Balle, B., Barthe, G., Gaboardi, M., Hsu, J., and Sato, T. Hypothesis testing interpretations and Rényi differential privacy. In Int. Conf. Art. Intelligence and Stat. (AISTAT), pp. 2496-259655 2506, 2020.
We thank the anonymous reviewers for their valuable feed- back, which significantly improved the quality of this paper. This work was supported by the National Science Founda- tion under Grant Nos. CIF-2312666 and CIF-2312667.
Bun, M. and Steinke, T. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Proc. Theory of Cryptography, pp. 635-658, 2016.
Impact Statement
Canonne, C. L., Kamath, G., and Steinke, T. The discrete Gaussian for differential privacy. In Proceedings of the 34th International Conference
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Neural Information Processing Systems, NIPS '20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546.
References
Chen, Y., Thakurta, A. G., and Woodruff, D. P. Pois- son subsampled rényi differential privacy. In Proceed- ings of the 52nd Annual ACM Symposium on Theory of Computing (STOC), pp. 849-860. ACM, 2019. doi: 10.1 10.1145/3313226.331166
Renyi DP mechanism design. https://github. com/ SankarLab Saliaaa/eeenDDea Stwprr--D---ecaaan---eeeeeee May 2025.
Abadi, M. Chu, A.. Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang. L. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Doroshenko, V., Ghazi, B., Kamath, P., Kumar, R., and Manurangsi, P. Connect the dots: Tighter discrete ap- proximations of privacy loss distributions, 2022. URL
https: /trpss:/arxiv...o hat//arxivv//// org/ /b0.//20.222003300
Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., and Naor, M. Our data, ourselves: Privacy via distributed noise generation. Vaudenay, (ed.), EUROCRYPT, pp. 486-503,220 2006a.
Abowd, J., Ashmead, R., Cumings- Menon, R., Garfinkel, S., Heineck, M., Heiss, C., Johns, R., Kifer, D., Leclere, P., Machanavajjhala, A., Moran, B., Sexton, W., Spence, M., and Zhuravlev, P. The 2020 Census Disclosure Avoidance System TopDown Algorithm. Harvard Data Science Review, (Special Issue 2), jun 24 2022. http:://ddst.mitprsss... hwt.:t/pwee....iiciuuuu/////i/i
Dwork, C., McSherry, F., Nissim, K., and Smith, A. Calibrat- ing noise to sensitivity in private data analysis. In Proc. Theory of Cryptography (TCC), pp. 265-284, Berlin, Hei- delberg, 2006b. ISBN 3-540-32731-2, 978-3-540-32731- 8.
Alghamdi, W., Asoodeh, S., Calmon, F. P., Kosut, O., Sankar, I.., and Wei, Cactus mechanisms: Optimal differential privacy mechanisms in the large-composition regime. In 2022 IEEE International Symposium on In- formation Theory (ISIT), pp. (188-18433 2022. doi: 10.1 www.9//STTS0066622222988844
Feldman, V., Acharya, A., Dinesh, P. N., and Rothblum, G. N. On the rényi differential privacy of the shuffle the
model. In Proceedings the 52nd Annual ACM Sympo- sium on Theory of Computing (STOC), pp. 1232-1244. ACM, 2021. doi: 14.1145/3460122.48877777
Alghamdi, W., Asoodeh, S., Calmon, F. P., Felipe Gomez, J.. Kosut, O., and Sankar, L. Schrödinger mechanisms: Optimal differential privacy mechanisms for small sensi- tivity. In 2023 IEEE International Symposium on In- formation Theory (ISIT), pp. 2201-2206, 2023. doi: N0.1109/SSTT4773322222 1120044771..22220000666666
Feldman, V., Liu, Y., Karpov, D. V., Muthukrishnan, S., and Kuczynski, J. Stronger privacy amplification by shuffling for rényi and approximate differential privacy. arXiv preprint arw.vv220..0459)) 2022. URL https: / //arxiv. www.iiiorrg//baa. abs /200 04591.
Geng, Q., Kairouz, P., Oh, S., and Viswanath, P. The stair- case mechanism in differential privacy. IEEE Journal of Selected Topics in Signal Processing, 9(7): 176-11444,, 2015. doi: 10.1109//SSSP22255522555
Asoodeh, S., Liao, J., Calmon, F. P., Kosut, O., and Sankar, L. Three variants of differential privacy: Lossless conver- sion and applications. IEEE Journal on Selected Areas in Information Theory, 21):2208 2021.
Ghosh, A., Roughgarden, T., and Sundararajan, M. Uni- versally
Balcer, V. and Vadhan, S. P. Differential privacy on finite computers. In Information Technology Con- vergence and Services, 2017. URL https://api: semant wwcholachhl...ocooooooooo ort.chooaar..ooo/oopopssooso
privacy mechanisms. SIAM
J. Comput., 41(6):1673- January 2012. ISSN
0097-5397. doi: 10.11377099766828x URL https:
/ //doi.org/10. http://....13700007110
10

---

Optimizing Noise Distributions for Differential Privacy
Janosi, A., Steinbrunn, W., Pfisterer, M., and Detrano, R. Heart disease data set. https://archist ics. HttHHHHattttttieeeeeeeee 1988. Accessed: 2025-04-29.
edu.mm/
learn developers, S. Diabetes dataset. https:
//sciktt-leam..org//tttt http://r/g//aaal/mmo/lleeee
generatedd/kleer...deee dat _oad
diabetes html. Accessed: 2025-04-29.
Lécuyer, M., Lee, M., Smith, A., and Vadhan, Practi- cal privacy filters and odometers with rényi differential privacy and applications to differentially private deep learning. arXiv preprint
2021. URL https: / //txxvvvvv//..////////..//aaaav. org/ abs//b/////g 2103. 01379.
Mironov, I. On significance of the least significant bits for differential privacy. In Proceedings of the 2012 ACM Conference on Computer and Communications Security, CCS 12, pp. 650-661, New York, NY, USA, 2012. Asso- ciation for Computing Machinery. ISBN 9781450316514. doi: 10. I 00.114422822119622222666 URL httpps:/dd.
10. org/ /1g/ 1111112222222 2382264.
Mironov, I. Rényi differential privacy. In Proc. IEEE Comp. Security Foundations Symp. (CSF), pp. 263-275, 2017.
Erven, T. and Harremos, P. Rényi divergence and kullback-leibler divergence. IEEE Transactions Infor- mation Theory, 60(7):3797-3820, 2014. doi: 10.1109/ TTT:2014.2320500..
Wikipedia. Moore-Penrose inverse
https:
10sssPenrose_inverseee a.
Wikipedia. Tonelli's theorem for non-negative measurable
functions wii . /wtg/w/ikke orgg/iiki / attp:/thoorreettooooeaaaaattttoo for for.noor-sgaiiieeeaaaaarrrbrdddd b.
Wolberg, W. H., Mangasarian, O. L., and Street, W. N. Breast cancer wisconsin (diagnostic) data set. https: //archive. ics. uci edu/ml/ //t.m//aaa//////////mamm (Diagnostic),
1993. Accessed: 2025-(4429.

---

Optimizing Noise Distributions for Differential Privacy
A. Proof of Theorem 3.1
Let 2 the domain of the query's output, which may consist of real numbers or integers, and let P(Z) denote the set of all probability distributions supported on Z. Let the distribution P-z represents the reflection of Pz with respect the g-axis, such that (-z(z) (=(-2) for all 2
The feasible region P, S P(Z) encompasses all noise distributions Pz P()) that satisfy the normalization constraint Eyy [1] 1, the positivity constraint (2(z) 2 0 for all 2, and
the cost constraint Epg [e{ 2) < C. The set S represent the possible shifts: specifically, S = -888] 8] if Z = R. and
S = (-s....,00 O, O,..., }) if Z = Z.
Recall that
Pz
a-1
9a (P2,t) =Ep,
(26)
TrP2
and
ga = =max Ia (P2, t). tES
(27)
To justify restricting the search to symmetric noise distributions, we demonstrate that the feasible region Pj is both symmetric and convex. Additionally, we prove that 9a (P2) exhibits symmetry in Z and convexity in Pz. By leveraging these properties, we establish that minimizing over the entire feasible region yields the same result as minimizing solely over the symmetric distributions within that region.
Convexity of the Feasible Region: Let À E (0, and Pz, Qz Py, we show that XPz + +1 X)Q2 E Py. The convex combination XPz + (1 x)Qz is valid distribution, as it satisfies the normalization constraint as follows:
BAP2+(1-X)Q [1] = x E [1] + (1 X) Eqz [1] 1,
(28)
and it is non-negative for all E i.., (2) + (1 ())z(z)
We also have
BAP2+ [c(Z)) = P (c(2)) + (1 A) Roz [c(2)] S AC (1-
(29)
The inequality holds because Pz, Qz E P,, and thus Erz [c(Z)] S C and E [c(2) S C. So, we have
APz (1 A)Q2 E P/.
and the feasible region P is convex.
Symmetry of the Feasible Region: We show that if Pz lies within the feasible region, its reflection P-z must also belong to the feasible region. If Pz E P(Z) (i.e., it is a non-negative. normalized measure), then P-z E P(Z). Thus, our focus is on verifying the cost constraint. Given that Pp [c 2)] < C, we need to show that Ep = [c(2)] < C' as well. We have
Ep_ [c(2)] = Ep [c( 2) Epz C
(30)
where the first equality follows from a variable change and the symmetry Z. The second equality follows from the symmetry of the cost function.
Symmetry and Convexity of the inner maximization: As shown in (van Erven & Harremos, 2014) (Proof of Theorem
a-1
13), the expression EpZ
is jointly convex Qz). In (26), with Qz = T.Pz and the linearity of Tr, follows that 9a (P2,t) t) convex Pz. Moreover, since the pointwise maximum over preserves convexity, ga (Pz)
Pz
QZ
also convex in Pz. We now show that ga (Pz) is symmetric follows:
9a (P-z) Ia (P-2tt
(31)
tES
P-z
a-1
max Ep_2 IES
(32)
TrP-z
Pz
max tES
Epz
(33)
T-
12

---

Optimizing Noise Distributions for Differential Privacy
Pz
a-1
max IES
Epz
(34)
T2P2
max LES
Ia (P
(35)
(Pz),
(36)
where (33) follows from the symmetry of Z and the variable substitution from - to while (34) results from the inherent symmetry of S.
Sufficiency of Restricting the Search to Symmetric Noise Distributions: Leveraging these properties, we now establish that it is sufficient to restrict the search to symmetric noise distributions. Let Pz be an optimal noise distribution; i.e., Pz minimizes 9n (Pz) over all Pz E Py. Also let M 9.( be the optimal objective value. Let (0, 1), since the feasible region is convex, we have
XP + (1 A)P"2 E Py.
(37)
Since ga (P2) is symmetric, we have 9a (P%) Pa MM, and so P is also an optimal noise distribution. Considering the convexity of (Pz), we have
9a (AP2
A)112) s Aga (P2) + (P=z)= AM + (1 A)M M
(38)
which means every noise distribution on the line segment connecting 122 and P is an optimal noise distribution. For the special case of X = 2. we get an optimal noise distribution
P2 + P
2
which is symmetric. This proves the existence of symmetric noise distribution among the set of all possible solutions and so the sufficiency of searching over only symmetric noise distributions.
B. Proof of Proposition 3.5
For the continuous case, we have
f c(z) fz(2) dz
Elc(Z))
(39)
JEEn
Pld d(2)
dz
(40)
A
NE VEL,
Σ Plil iE
f d(2) dz
(41)
A
JEL,
N-1
Po
c(2) dz +2
Σ
Pi
d(z)
dz +
PN ii
c(2) dz
(42)
A
SEIo
i=1
A
=EI;
im N
A
sEL,
N-1
= Ao +2
Σ
P:A; + 2pp
Ai
(43)
i=1
i= N
where
A,
c(2) dz,
(44)
A =El1
and (42) follows from the symmetry of c(z). When c(2) 22, Ai simplifies to:
1
/
2
(i ) (i ) 13
==²(+11))
(2+ 1
A;
d
(45)
A sEL.
12
13

---

Optimizing Noise Distributions for Differential Privacy
and
Pb42
N
1
Var Z)
2
Pi
A 2
2 +
+
2PN
N
i +
(46)
12
12
12
i=1
i=
A
DO
Po
2ps +
2p
+2 Σ
Pr A
2pN
(47)
12
i=N
i=N
A
N N-1 Σ
2PN
N-1
00
Po
+
2p,
+
2
pj 2 + 2pn Σ
1- 22
(48)
12
1-r
(=1
1=1
i=N
A
N-1 Σ
+
2
Ps
12 + 2p A
Σ N=
N
(49)
12
1=1
where (49) follows from the normalization constraint in (16), and we have
30
2 (N 1)2 22 2r) + r2NN + 1)
Σ
(50)
r13
The proof for the discrete case follows similar approach.
C. Proof of Theorem 3.6
Here, we present a proof for the continuous case. The proof for the discrete case follows a similar approach to that of the continuous case. Recall that in the continuous case, the PDF is given by
fp.....()) = Pi for z E I, iith E Z.
(51)
A
where 1, (i) (i+ +)4), p- Pt, and p: PNr for |i| 2 N. To simplify the expression inside the logarithm of the RDP, as presented in (12), we begin by substituting the piecewise-constant form of the PDF and simplifying it for any shift & [-s, s). After substitution, the resulting expression becomes piecewise linear in t, with breakpoints occurring when / is multiple of the bin width A, aligning the bins of the PDF and its shifted version. Thus, to find the maximum over f, we only need to consider the breakpoints within [-s, s] and the interval's 's endpoints, forming a finite set of candidates. Finally, we simplify the expression for each element in this finite set.
For the continuous case, we have
ga Ja( = (pm.Nsss)) Sp..N.(2 - (pn.M.az--t)t-a 1)
(52)
1-a
/
Σ
8
Pi A
1(2e11)
Σ
8
Di
1(2 1 -t
dz
(53)
5=-00
1
1
1)-a 15T;) dz
(54)
A
==-00
1
p
1f2 E 1i] 1f2 - - E 11} dz
(55)
A
1 8
/
Σ
13 112 te 43) dz.
(56)
A
-=-
Equation (56) follows from applying Tonelli's theorem for non-negative measurable functions (Wikipedia, b) twice. This holds true because both the Lebesgue measure on the real numbers and the counting measure on the integers are o-finite,
and the expression pf 1 (2 E 7.) 1(2 t E T,} is non-negative for all í,j E and z E IR. The integral within the
14

---

Optimizing Noise Distributions for Differential Privacy
expression above be simplified follows:
| 4/1f2 - t dz
(57)
otherwise
((+0- (i-
+ ( ft& ((i-j) - (+
(58)
Substituting the expression from (58), the expression in (56) simplifies to:
/
P
(59)
A
1=-00 1=
00
00
Σ
Σ
Pi Pj
((=6-i-1)))((
((i- 1)4,
1=
+(-t+A(i -
((i- ((i (i
(60)
1-a Pmtj P/
a
(L+ 1) fe ((m - 1)4, mA]}
1 - Do M==
+ (-++ + 1) (mA, (m + +)A)}
(61)
where, in (61), we apply the variable change m i for each fixed j. Since is a real number the interval [-s, s]. the indicator functions 1 {t ((m 1)A, mA]} and 1 {t (mA, (m + 1)4)} are zero for values of m outside the set A O, where A is chosen such that is integer. Therefore, go (Jp.r,N,A..) simplifies to:
A
20
ga(Fp..NNA,,))
Pm+j
1-a (t (++ 1)A) ((m- 1)A, ma]}
-=-00 m=
+-+++ (m++ 1) ( + 1)A)}
(62)
To solve the maximization problem over t E [-8, s], observe that the above expression is piecewise linear in t. Therefore, sufficient to evaluate the maximum at the endpoints of the linear segments. These endpoints are given by Let evaluate the expression in (62) aA:
aA aE
A
Da (p....
Pmntj Pj 1-a
(aL + (-m+ (as E ((m
m=
+ (-aA + (m + 1)A) 1 fad E (mA, (m + 1)1)}
(63)
20
Σ
Pot pj (aA + (-a+1)A)
(64)
A j=
20
Σ
Pa+j p 1-a
(65)
-0
15

---

Optimizing Noise Distributions for Differential Privacy
minf -N-1--
max oo
Σ
(PN P------ (pN -ー---
Σ
Patj Pj aa
10-00
j=min| -N - -Na.-N
(pN ya (pN N-N
(66)
j=max -
min Main--N-ar0 -N.------
max N.N-aa Σ
PN -a-N
Pats EjjjP - +NN paa-N
(67)
f=min(-No -N-a.-
j=max NNN
PN r -a-N min -onnt-N-o,-he N
max NN)
Pats Pj a + PN paa-N N m [.nxx|NN... -N,N-
Σ
(68)
j=mia -NN--NN
max
PNT
(-o0-NNmaxx(Ma.)) + po - NNNmax(NNNaa))
Σ
Patj Pj
(69)
1-
/=min -N -Naa--N
max NN.(NNN-a)
PN r
(roaataxx(a.) + (0 +
Σ
Pats Pj
(70)
--r
j=min(- Maainn--Ne,----
N N-lal
PN r
(f0-o)]ol pllll
Σ
Pial-j Pj
pf:r0((a1-N)
-=ー
N
-
Σ
p p3
Pj
a-
+
PN
a a(1-a)
Σ
Pl
Pial+s r i(1-a)
lia + 0}
(71)
N
j= -N
where (64) follows because open interval (m1, (m + 1) does not include any endpoints. So
foA E (mA, (m + 1)A)}
and a half-open interval ((m - 1)4, mA] includes the endpoint aA if m a. The equality (71) follows because
r-at+ paa if 2 0 -0 + pan-a
maatmax(a.)) aacaaa000ppppataaaaaaaaa aax+max -a)
=-(1-a)ee paaal
(72)
if < 0
and
max MAx(NNN-O) -a
Σ
Po+s Pj 1-a
(73)
j=min(-N Monin--N-a,NN
-N-1
paat p.-00 10- + PN 1-a, NN(-a)
plaltj )(10-)))
11a + 0}
(74)
-alaa -
N N-
N
Σ
Plat+s P3 p + ppr a(al-()
p p! 1-a
N
-
-
+
p
Σ [a|
Pialts r 5(1-a)
1fa 1fa + 0}.
(75)
where we have used the assumption that the distribution is symmetric, meaning P: = P-i- The quantity in (71) is symmetric with respect to a; therefore, the maximum over
tE as a E {
$ } A
A O.
16

---

Optimizing Noise Distributions for Differential Privacy
Laplace ace
RDP noise
Gaussian
Staircase
Cactus
5.0
4.0
3.0
2.0
1.5
1
10
15
20
25
30
35
40
45
50
55
60
Compositions
Figure 6. For fixed = 10 the grid evaluates different combinations of composition count and noise standard deviation (o), marking RDP noise as the winner whenever achieves more than a 2% improvement in e over the best alternative (among Gaussian, Laplace, Staircase, and Cactus). Even when another distribution is marked the best, noise still consistently outperforms the others, although by less than 2%.
reduces to maximum over
E a a a
$11 A
and |a| simplifies to a. Moreover, when 0, the two distributions identical, and the divergence reaches its minimum value of zero. Hence, we can exclude = 0 from the set. So, the task of finding the worst-case shift collapses to the following optimization:
N-a
PN r
(f(1-a)o + ,au)=
Σ
p/_a + aaara
max a 1....
Pots Pj
--r
j=-N
-N-1
raj pj-a + PN a- -NO-NN11000 a))
Σ
Patz r r-11 j()-a)
(76)
j=N-ot1
j=-a-N
Utilizing the symmetry of the noise distribution (pi p-i), rewrite the maximization follows:
N-a
PN
(xil-ajaa + tr))
Σ
Platsi 1-a + p2y p(a-)
max
-N-1
pas P(jl 1-a
+ a N(1-a)
Σ
Pla+s| r j(l--a)
(77)
J=
jm-a-N
D. Additional Numerical Results
The region of compositions and noise levels (α) where optimized noise achieves at least 2% improvement in standard mechanisms (Gaussian, Laplace, Staircase, and Cactus) shifts as 8 changes. Figure 6 presents plot similar to Figure 4 but for 8 = 10- These results further highlight that the optimal noise distribution is highly getting-dependee Since our RDP noise consistently performs well across different settings and avoids the need for manual selection among existing mechanisms, it offers more reliable default.
Figure shows a plot similar to Figure 5, but for smaller a = 5, with number of compositions fixed at 10 both cases. As shown, the range of where our method provides the greatest improvement shifts with the choice of a. For 5 (Figure 7), the peak improvement occurs between = 2 and 2.8, while for the larger 8 in Figure 5, it lies between approximately 1.2 and 1.8. This shift is expected-optimizze for a larger corresponds to higher privacy regime, resulting in smaller values.
To obtain the results in Table 1, we assume that the 5th and 95th percentiles of each feature are privately released. These quantiles are used to rescale each feature by subtracting the 5th percentile and dividing by the difference between the 95th and 5th percentiles. This transformation maps most feature values the [0, 1] range, and any values outside this range are
17

---

Optimizing Noise Distributions for Differential Privacy
107
10a
10
10
10
10
10
10
10
10
10
RDP naise (pointwise min)
Discrete RDP noise (pointwise min)
10
Staircase
Discreto Staircase
Cactus
Discrete Cactus
10"
Gaussian
Discrete Gaussian
Laplace
Discrete Laplace
10-1
0.5
1.0
15
2.0
2.5
10
1.0
1.5
2.0
2.5
3.0
3.5
Figure 7. The plots compare the pointwise minimum of privacy curves from our optimized noise distributions-desieeee for 10 composi- tions, sensitivity I, and varying d-with privacy curves for Gaussian, Laplace, Cactus, and Staircase mechanisms, all with a fixed standard deviation of 5. The left plot shows continuous distributions; the right plot shows discrete distributions. All curves are evaluated at 10 compositions.
clipped to 0 or 1. This normalization step ensures that all features are consistent scale before noise is added. Mapping back to the original feature scale can be done using the privately released quantiles.
Since the quantile release step incurs the same privacy cost for both the Gaussian and RDP noise mechanisms, we do not account for it separately in our analysis. Instead, we focus on evaluating the privacy-utility trade-offs introduced by the noise-adding mechanisms themselves.
We then add noise using either the Gaussian mechanism or our optimized RDP noise. For each query, we generate 100,000 differentially private outputs by adding noise according to the selected mechanism and compute the mean squared error (MSE) with respect to the true (non-pol (non-private) value. We average the MSEs across 10 queries, repeat the process for 20 random seeds, and report the mean and standard deviation (+) of the improvement over Gaussian noise.
For the remainder of this section, we provide details about the datasets and the queries used in the experiments presented in Table
Breast Cancer Wisconsin (Diagnostic) (Wolberg et al., 1993): This dataset contains 569 records with 30 continuous features extracted from digitized images of fine needle aspirates of breast masses. These features capture various properties of cell nuclei, including radius, texture, perimeter, area, smoothness, and symmetry. We define 10 continuous queries, each computing the average of key diagnostic indicator. These include the overall average values of features such as mean radius, texture, area, smoothness, and fractal dimension. Such queries are commonly used in biomedical research and medical data analysis to support disease characterization and model interpretability in diagnostic applications.
Diabetes dataset (learn developers): This dataset includes 442 patient records and 10 features representing physiological variables such age, sex, body mass index (BMI), blood pressure, and six blood serum measurements (s1 to s6). We define 10 continuous queries, each computing the mean of feature across the dataset. These queries capture the average body mass index, blood pressure, age, sex indicator (reflecting gender distribution), and the average values of each of the six serum biomarkers.
UCI Heart Disease Dataset (Cleveland subset)(Janosi et al., 1988): A widely used clinical dataset containing diagnostic information for 303 patients undergoing evaluation for coronary artery disease. includes a mix of demographic and clinical features such as age, sex, resting blood pressure, serum cholesterol, maximum heart rate achieved during exereise. and indicators of exercise-induced angina. To simulate realistic medical analytics, define 10 queries focused patient demographics and cardiac health metrics. These include the average age and maximum heart rate within subgroups defined by sex and angina status, as well as the average resting blood pressure and cholesterol levels for higher-risk populations, such as individuals with hypertension or adults over the age of 55.
18


Reviews:
[{"review_id": "7c6YAbhFvM", "reviewer": "Reviewer_WDdd", "summary": "The paper proposed a novel framework for optimizing noise distributions for (epsilon, delta)-DP using the Renyi differential privacy formulation. Experiments are shown to showcase the benefits of the approach.\n\nOverall: The paper is easy to follow and the main results are well laid out. The experimental results are not particularly convincing in terms of the practicality of the proposed approach.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n**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.**\n\nWe 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.\n\nIn 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.\n\n**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.** \n\nWhile 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. \n\nSome 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.\n\n**Q3 ) How do you think this framework would apply to real-world applications? Will there be substantial gains over Gaussian or Laplacian distributions?** \n\nAs 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.\n\nIf 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.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes and no, see below.", "theoretical_claims": "Yes, proposition 3.5 and Theorem 3.6", "experimental_designs_or_analyses": "Yes, check below.", "relation_to_broader_scientific_literature": "See below", "essential_references_not_discussed": "They are mostly covered", "other_strengths_and_weaknesses": "Pros:\n\n(i) The setting is highly interesting and it answers the question of how to select the optimal distribution for the specific problem at hand.\n(ii) The utilization of the Renyi DP formulation and the subsequent minmax problem with the proposed convex optimization/solver are interesting. In particular, each of these are rigorously proved by the presented Theorems/propositions. \n(iii) The experiments show how the optimization finds the best of the Gaussian and Laplacian regimes and in some cases is better than both.\n\nCons:\n\n(a) 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.\n(b) 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.", "other_comments_or_suggestions": "See below", "questions_for_authors": "(1) How do you think this framework would apply to real-world applications? Will there be substantial gains over Gaussian or Laplacian distributions?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "x8YF4wftH4", "reviewer": "Reviewer_TUrb", "summary": "The authors of the paper introduce an optimization framework that optimizes noise distribution for $\\alpha$-RDP, where the optimal distribution can be obtained by a finite-dimensional convex optimization problem. Their main contribution is the proposal of optimized distribution for a moderate composition regime (single/large cases are already shown in previous works).\n\nFor their objective, they first formulate an optimization problem for **minimizing $\\alpha$-Renyi Divergence for a given constraint (e.g., variance of the distribution)**. \nThen, they show that the problem is convex and symmetric.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n**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).**\n\nWe 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.\n\n**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.** \n\nWe 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. \n\nAs 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. \n\n**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).**\n\nWe 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. \n\n**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?**\n\nWe 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.", "claims_and_evidence": "Throughout the paper, the authors introduce their contributions very clearly. Also, the experimental results clearly show the superiority compared to Laplace and Gaussian mechanisms.", "methods_and_evaluation_criteria": "Since the aim is to minimize the value of $\\epsilon$ for a given value of $\\delta$ and variance bound $\\sigma$, the evaluation criteria is proper.", "theoretical_claims": "The reviewer checked the correctness of the proofs for theoretical claims for Theorem 3.1. and Proposition 3.5", "experimental_designs_or_analyses": "The reviewer has a question about the experimental design, especially for baselines. Please refer to the “Question for Authors” Section.", "relation_to_broader_scientific_literature": "Previously, noise distribution optimizations for differential privacy have been discussed for a single composition or a large number of composition regimes, where the optimal strategies are stair-case and cactus mechanisms, respectively. The authors propose a general approach that can be used for all regimes.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "Throughout the paper, the authors clearly introduce the novelty of their work, as well as their mathematical contributions. The preliminaries part is well-written. The idea of min-max optimization is interesting, and the approach provided in this manuscript is novel.", "other_comments_or_suggestions": "Here are my minor concerns; please refer to the next section for more detailed reviews. \n- In the preliminaries (line 120-130), the definition of $\\sim$ is duplicated ($X\\sim P$ for probability distribution and $d\\sim d’$ for the neighboring sets). \n- 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).", "questions_for_authors": "- 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 Stair case and Cactus mechanisms.” However, the reviewer cannot find the related experimental results.\n- 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).\n- Are there any additional practical examples regarding moderate composition regimes other than U.S. Census Bureau? \n- 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?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RG02qf0uys", "reviewer": "Reviewer_AB3E", "summary": "This paper addresses the optimization of noisy distributions under the RDP framework. Compared to classic approaches, such as Laplace or Gaussian mechanisms, the derived distribution achieves a lower overall cost.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's thoughtful feedback. Below, we provide detailed responses to their concerns.\n\n**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?** \n\nWe 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.\n\nFrom 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.\n\nWe 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).\n\n**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.** \n\nWe 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.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "See the pros below.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Pros: The problem is important, and the proposed approach is compelling.\nCons: Please refer to my questions for further details.", "other_comments_or_suggestions": "See the question below.", "questions_for_authors": "1. From the numerical results presented in the figures, it appears that there is little difference for smaller values of $\\epsilon$ (e.g., $\\epsilon < 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?\n\n2. 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.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "trPUxsqoEz", "reviewer": "Reviewer_zWjf", "summary": "The paper studies non-canonical (i.e., not Laplace or Gaussian) noise distributions for answering $d$ queries under $(\\varepsilon, \\delta)$-DP. It casts the overall problem as follows: the user provides $\\delta$, $d$, and the sensitivity and error constraint $\\sigma$ for each query. Then the provided algorithm formulates this as a convex optimization problem over discrete (or \"morally\" discrete) Renyi DP noise distributions that can be represented as finite real vectors and applies a carefully chosen optimization algorithm to solve for a distribution achieving the minimal possible $\\varepsilon$. Depending on the provided user inputs, the resulting algorithm can produce distributions that achieve noticeable improvements over Laplace and Gaussian noise.\n\n## update after rebuttal\nI've increased my score to weak reject. The author response resolved my questions about parameters, numerical stability, and the relationship to the staircase mechanism (and I'd suggest to the authors to add these discussions to the next version of the paper). I don't think it's clearly wrong for the paper to be accepted. However, to me the small degree of improvement, the opacity of the eventual distributions, and the need to use connect-the-dot accounting for each new problem instance limit how useful the results are theoretically or practically.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive feedback. Below are our responses to their concerns.\n\n**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).\n\n**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.\n\n**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.\n\n**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.\n\n**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.\n\n**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.", "claims_and_evidence": "The abstract claims \"significant[ly]\" better privacy guarantees than the Laplace and Gaussian distributions in some parameter settings. \"Significant\" is subjective, but the improvements appear to range from ~0 to 9%, with the latter occurring in a somewhat narrow portion of the parameter space, with some further questions about baselines (see boxes below). I think the significance is questionable.", "methods_and_evaluation_criteria": "The form of the experiments provided, mostly plots involving some combination of $d$, $\\varepsilon$, $\\delta$, and $\\sigma$ seems reasonable.", "theoretical_claims": "I didn't check any of the proofs. The basic ideas seem reasonable.", "experimental_designs_or_analyses": "The paper omits a few things that I think should be discussed.\n\n1) How is $N$, the support size of the distribution, chosen? What is its value in the experiments? What about $r$, $K$, and $T$?\n\n2) How easy/fast are these algorithms to run relative to their simple Laplace and Gaussian counterparts? Runtime doesn't appear to be discussed anywhere (or I missed it).\n\n3) If I remember correctly, the staircase mechanism dominates the Laplace mechanism, particularly for large $\\varepsilon$. The paper claims that its optimization recovers the staircase mechanism in the single composition regime but otherwise omits it. It seems like the staircase mechanism should replace the Laplace mechanism in the experiments, especially since the figures show the largest improvements at large $\\varepsilon$, where the staircase mechanism should also improve over the Laplace mechanism. Concretely: is the returned distribution at these settings just the staircase mechanism?\n\n4) Can you say a bit more about possible numerical issues? The optimization problem described in Theorem 3.6 looks like it may have under/overflow issues. This is especially relevant because the DP guarantee of the algorithm is entirely dependent on the optimization working correctly.", "relation_to_broader_scientific_literature": "The general idea of solving an optimization problem to find a private additive noise distribution is (as the paper notes) not new. To the best of my knowledge, this formulation in terms of ~finite discrete distributions has not been studied before. I think the paper is at least moderately novel.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "(See other responses.)", "other_comments_or_suggestions": "(See other responses.)", "questions_for_authors": "In addition to questions 1)-4) written above, I'll ask:\n\n5) What do the authors think this algorithm \"tells us\" about DP? It returns what the authors claim is a new and better kind of distribution, but I'm curious what form the distribution takes. In addition to the question above about its relationship to the staircase mechanism, it would be interesting to see approximately what shape the distribution has, or other properties that might explain its improvement over baselines. Without that, it's hard to say how just knowing that the distributions exist improves our understanding of DP.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper makes novel contributions to the development of optimal additive noise distributions for differential privacy. The work is well-presented, appears sound, and may yield nontrivial improvements for real-world applications.

There are some limitations: the gains are relatively modest, there are a number of hyperparameters to be set when implementing the optimization algorithm, and the resulting noise distributions are somewhat opaque and may be hard for practitioners to grasp intuitively. The conceptual novelty is also limited, in the sense that the results don't seem to provide a lot of new fundamental understanding. Still, in settings with a fixed metric and strict budgets, the methods here look promising.

The authors should follow through on the changes promised in response to reviewer questions (comparisons with the staircase mechanism, additional results, etc.), as these will significantly enhance the paper.
Decision: Accept (poster)