Dirichlet Mechanism for Differentially Private KL Divergence Minimization
Authors: Donlapark Ponnoprat
Venue: Accepted by TMLR ()

Abstract: Given an empirical distribution $f(x)$ of sensitive data $x$, we consider the task of minimizing $F(y) = D_{\text{KL}} (f(x)\Vert y)$ over a probability simplex, while protecting the privacy of $x$. We observe that, if we take the exponential mechanism and use the KL divergence as the loss function, then the resulting algorithm is the $Dirichlet\text{ }mechanism$ that outputs a single draw from a Dirichlet distribution. Motivated by this, we propose a Rényi differentially private (RDP) algorithm that employs the Dirichlet mechanism to solve the KL divergence minimization task. In addition, given $f(x)$ as above and $\hat{y}$ an output of the Dirichlet mechanism, we prove a probability tail bound on $D_{\text{KL}}  (f(x)\Vert \hat{y})$, which is then used to derive a lower bound for the sample complexity of our RDP algorithm. Experiments on real-world datasets demonstrate advantages of our algorithm over Gaussian and Laplace mechanisms in supervised classification and maximum likelihood estimation.

Published in Transactions on Machine Learning Research (02/2023)
Dirichlet Mechanism for Differentially Private KL Divergence Minimization
Donlapark Ponnoprat
donlapark, pociuparr.p@mu....o ac.th
Department Statistics
Chiang Mai Universily
Reviewed on OpenReview: https: // openreview. net/ forum? id= 1mr2wul aFc
Abstract
Given an empirical distribution f(x) of sensitive data we consider the task of minimizing Fly) = DKL(f(r))
over a probability simplex, while protecting the privacy of æ. We observe that, if we take the exponential mechanism and use the KL divergence as the loss function, then the resulting algorithm the Dirichlet mechanism that outputs a single draw from Dirichlet distribution. Motivated by this, we propose a Rényi differentially private (RDP) algorithm that employs the Dirichlet mechanism to solve the KL divergence minimization task. In addition, given f(z) above and mechanism, we prove probability tail bound on (f which is then used to derive a lower bound for the sample complexity of our RDP algorithm. Experiments on real-world datasets demonstrate advantages of our algorithm over Gaussian and Laplace mechanisms in supervised classification and maximum likelihood estimation.
output of the Dirichlet
1 Introduction
KL divergence is the most commonly used divergence measure in probabilistic and Bayesian modeling, In a probabilistic model, for example, we estimate the model's parameters by maximizing the likelihood function of the parameters, which in turn is equivalent to minimizing the KT. divergence between the empirical distribution and the modcl's distribution. In supervised classification, standard way fit classifier is by minimizing the cross-entropy of the model's predictive probabilities, which is equivalent to minimizing the KL divergence between the class-conditional empirical distribution and the model's predictive distribution.
Such models are widely used in medical fields, social sciences and businesses, where they are used to analyze sensitive personal information. Without privacy considerations, releasing a model to public might put the personal data at risk of being exposed to privacy allacks, such as membership inference al al (Shokri et al., 2017 Ye et al. 2022 To address the model's privacy issue, we should focus on its building blocks: the KL divergences. How can we minimize the KL divergence over the model's paramcters, while koeping the data private?
Differential Privacy (Dwork al. 2006a b) provides a framework for quantitative privacy analysis algorithms that run on sensitive personal data. Under this framework, one aims to design a task-specific algorithm that preserves the privacy of the inputs, while keeping the "distance" between the privatized output and the truc oulput sulficiently small. A simple and well-studied technique is to add small random noise sampled from a zero-centered probability distribution, such as the Laplace and Gaussian distributions. Another technique is to sample an output from a distribution, with greater probabilities of obtaining points that are closer to the true output, such as the exponential mechanism (McSherry & Talwar 2007 These techniques have been deployed in many privacy-preserving tasks, from simple tasks such as private counting and histogram queries (Dwork al. 2006a b) to complex tasks such as deep learning (Abadi al. 2016).
In this work, we are interested
sotting where our algorithm outputs an empirical distribution fa) of some sensitive data æ. To protect the privacy of individuals in æ, we keep f(x) hidden, and instead release another discrete distribution that approximates f(x in KT. divergence. This setting may not arise, for example, in

---

Published in Transactions on Machine Learning Research (02/2023)
the task of releasing a normalized histogram, the distance between histograms is often measured in e' or f². Nonetheless, there are many tasks where KT. divergence arises naturally. Prominent examples are those in probabilistic modeling, where the outputs the model's estimated parameters are obtained from likelihood maximization. Another examples are those in Bayesian modeling, where models are evaluated with adjusted negative log-likelihood scores, such as the Akaike information criterion (ATC) and Bayesian information criterion (BIC). It is also increasingly common in Bayesian practice to evaluate the model with out-of-sample log-likelihood (Vehtari et al. 2016). Again, minimizing these criteria can be formulated as minimizing the KL divergence.
A simple approach to privatize discrete probability distribution is by adding some random noises from a probability distribution. However, the KL. divergence does not behave smoothly with the additive noises, the following example illustrates: consider count data of 10 people, interpreted a normalized histogram: p == (0.1, 0.9). Suppose that we draw two sets of noises 21 ( (-0.090, 0.045) and 22 = (-0.099, -0.038) from (aplace(1/100 Here, the El-distances between and its noisy versions are 0.135 and 0.137, a very small difference. On the other hand, the KL divergences between between p and its noisy versions are 0.186 and 0.499, a 2.68 times increase. This example illustrates that adding noises to a discrete probability vector, even at a small scale, could result in a noisy vector that is too far away from the original vector in terms of KL divergence.
We instead consider the exponential mechanism, a differentially private algorithm that approximately minimizes user-defined loss functions. It turns out that, by taking the loss function to be the KL divergence, the exponential mechanism turns into one-time sampling from Dirichlet distribution; we shall call this the Dirichlet mechanism.
The Dirichlet mechanism, however, does not inherit the differential privacy guarantee of the exponential mechanism: the guarantee in (MeSherry & Talwar 2007) requires the loss function to be bounded above, while the KL divergence can be arbitrarily large. In fact, using the original definition of differential privacy (Dwork ct al. 2006b), the Dirichlet mechanism is not differentially private (sce Appondix A]. We thus turn to a relaxation of differential privacy. Specifically, using the notion of the Rényi differential privacy (Mironov we study the Dirichlet mechanism and its utility in terms of KL divergence minimization.
2017
1.1
Overview of Our results
Bclow are summarics of our results.
Privacy. We propose a version of the Dirichlet mechanism (Algorithm D that satisfies the Rényi differential privacy (RDP). In this algorithm, we need to evaluate a polygamma function and find the root of a strictly increasing function. Our algorithm easy to implement, as polygamma functions, root-finding methods and Dirichlet distributions are readily available in many scientific programming languages.
$
4 Utility. We derive a probability tail bound for DKI. (pllg) when q is drawn from a Dirichlet distribution (Therrmm 2). From this, we derive a lower bound for the sample complexity of Algorithm ! that attains a target privacy guarantee, both in general case and on categorical data.
$5 Experiments. We compare the Dirichlet mechanism against the Gaussian and Laplace mochanisms for two learning tasks: naive Bayes classification and maximum likelihood estimation of Bayesian networks both tasks can be done with KL divergence minimization. Experiments Dirichlet mechanism provides smaller cross-entropy loss in classification, and larger log- likelhoold in parameter estimation, than the other mechanisms at the same level of privacy guarantec.
real- world datasets show that the
1.2 Notations
In this paper, all vectors are d-dimensional, where d 2 2. The number of observations is always N. Let [d] = [l,.., d]. For any E Rd, we let i; be the i-th coordinate of u, and for any vector-valued function x + Rd, we let fi be that i-th component of f. Let R be the set of d-tuples of neg-tegative real numbers, and R&o be the set of d-tuples of positive real numbers. Denote the probability simplex by
sd-1 = {p Rd Σp =1].
2

---

Published in Transactions on Machine Learning Research (02/2023)
For any u, u' Rd and scalar >> 0, write + u (u1 + uq...... Ue 4/a) and ru = (rui,... ..... rud)). For
any positive-valued functions f,J", the notation f(x) ('(x:) means f(x) = Cx) for some constant C 0
and f(r) x f'(z) means cz) S f(z) S (x) for some c, C' > O. Lastly, ||u|22 = V + u is the l norm of u and |o = max; [4] is the 8 norm of u.
2
Background and related work
2.1 Privacy models
We say that two datasets are neighboring if they differ on a single entry. Here, an entry can be a row of the datasets, or a single attribute of a row.
Definition 2.1 (Pure and Approximate differential privacy (Dwork et al. 2006a bj). A randomized mechanism X + y is (e, -idffeerreyt private ((s, 6)-P) if for any two neighboring datasets æ and a' and all events E C V
Pr[M(a) EJ S (z)) E E] 6
(1)
If M is (s,D)-DP then say that it is e-differential private (e-DP).
The term pure differential privacy (pure DP) refers to e-differential privacy, while approzimate differential privacy (approximate DP) refers to (e, 8)- when 8 0.
In this paper, we shall concern ourselves with Rényi differential privacy, a relaxed notion of differential privacy defined in terms of the Rényi divergence between M (x) and (z'):
Definition 2.2 (Rényi Divergence (Rényi 1961 ). Let P and Q probability distributions. For À E (1, the Rényi divergence of order between P and Q is defined as
P(1)A~11)
Dx(PIIQ) = X-1 log y~P
E
Q(v)) 1-1
and for A == 1, we define (P(II)) DKL(PI)))
Definition 2.3 (Rényi differential privacy (Mironov 2017 ). A randomized mechanism M X" + y is (A,e)-Rényi differentially private ((AP))-DDP) for any two neighboring datasets and x',
(x(M())))((')) Se. So.
Intuitively, controls the moments of the privacy loss random variable: distributed as M(x), up to order X. smaller and larger À correspond lo a stronger privacy guaranlee.
log P[M[''=Y] where Y is
PlM())
The following composition property of RDP mechanisms allow us to track the privacy guarantees of using multiple Dirichlet mechanisms. This can be helpful when Dirichlet mechanisms is employed in a more complex algorithms, such as fitting a discrete probabilistic model.
Lemma (Composition of RDP mechanisms (Mironov 2017 Let Mi X2 + y be (A1, mechanism and M2 : X + Z be a (A2, -RDP mechanism. Then a mechanism M : X + +yx x Z defined by ((x) = (M)()) M2(x)) is (min(X1, X2), 61 + RDD.
2.2 Exponential mechanism with the KL divergence
The exponential mechanism (MeSherry Talwar 2007) is a privacy mechanism that releases an clement from range y that approximately minimizes given loss function f: N ) R. Given base measure I over y and dataset e N the mechanism outputs y E y with probability density proportional to:
-B((a.)) p(y),
where 3 is function of e, the privacy parameter.
For the first time, we point out the connection between the exponential mechanism and a well-known family of probability distributions under specific choice of f(x, v)- Let N Rd. be arbitrary vector-valued
3

---

Published in Transactions on Machine Learning Research (02/2023)
function datasets. Let y S Assuming that N₂ f((z) is known and nonzero, we denote the normalized vector f(x) - N f(x) (()) E S In equation 2 let ((x, v) = (f())l))))) & rN and p(y) be the density of Dirichlet(a)), that is, ply) & 1 v Then, the probability density of the output y of the corresponding exponential mechanism proportional to:
oxp(-rNyDKL II of exp
Σ
f((z) (o(x))
Il
1,2,300
x
1/$
1/
i,0.700
+a))
which is exactly the non-normalized density function of (1)) + a). This specific distribution will play major role in the main privacy mechanism introduced in the next section.
From this derivation, we can see that this particular instance of the exponential mechanism can be used to output y that approximately minimizes the KL divergence DKL (f())ly) while koeping æ private.
To see how the choices of r and a affect the "distance" between y: and f((x), we treat y; as an estimator of fz) and look the bias of yı:
(x(( +a rN, + da N, = Ny(rN, +a)
J((x))
-
E Elu
f(()))
(3)
The bias is reduced when increases and decreases. We can also look at the variance of y::
(rfi(x) a)(((N, f(())) + (d 1)a)
Var[y:
(rN, + (r) + da + 1)
which is 0(1/r) as + xo and O(1/a) as - co. This implies that draws from (r + a) are more concentrated when r and a are large.
Applications. The derivation of the Dirichlet mechanism above suggests that the best use of the Dirichlet mechanism for privately minimizing KL divergence, which arises in the following scenarios:
Maximum likelihood estimation. Consider a problem of parameter estimation in a multinomial model with d possible outcomes. Let æ E [d] be N observations, fi)),, ((.)),...,ffl.. fa(x) be the frequencies and yı..... fa be the model's parameters. Then the log-likelihood of x is f, fi fz( log Maximizing the log-likelihood with respect. to y is equivalent to minimizing the KT. divergence:
f(x)
arg max
Σ fz(z) log y: = arg min DKL
(0)
N
y
Thus, can use the Dirichlet mechanism to release the parameters of the model while keeping x private.
2. Cross-entropy minimization. Consider the same multinomial model as above. One might instead aim to minimize the cross-entropy loss: - 1 Σ, f((x) log y over y. This also equivalent to minimizing the KL divergence, so we can use the Dirichlet mechanism to privately solve for y.
Private estimation of a discrete distribution. unknoun discrete distribution p E gd-1 with p; > 0 for all i, a single draw y Dirichlet + a) can be used privately estimate p in KL divergence. The KL divergence between p and y can be bounded as follows:
we further assume that r is a sample from an
4

---

Published in Transactions on Machine Learning Research (02/2023)
DKL(Plle) = DRL - (xI(((=))pp) + E(er - fi(x)) log(pi/)))
- (PL(f())ll)) + max(log(ps/uu)
Eiri()) - psl-
(4)
Here, we sketch a proof that, with high probability, the bound is small for a sufficiently large Ny. Due to Theorem below and Agrawal (2020) Theorem I.2), respectively, both (J (ly)
and (f)((()) are small w.h.p. Combining this with Pinsker's inequality: E.lf(()) qa
22DKI. (f()))l), with q = y and p, we obtain R fi(z) se Pi, and so the second term is also small w.h.p. Note that we also have a similar bound for DKL (yl(v)p) by switching and p in equation 4 However, if some of the p.'s are really small, it will take a large number of data points to bound the logarithmic term equation Finding finite sample bounds for (RL(p)y)) and (yl(y)lp) an interesting problem that leave open for further investigation.
2.3 Polygamma functions
In most of this study, take advantage of several nice properties of the log-gamma function and its derivatives. The polygomma function of order m is the (m + 1)-th derivative of the logarithm of the gamma function. Specifically, when m = O, we have the digamma function vb(x) = d de Iog[(z)) [(x), which is a concave and increasing function.
Our function of interest is the polygamma function of order 1: (x), which is a positive, convex, and decreasing function (see Figure Th. It has the serics representation:
Figure 1: A plot of (/((x)).
(x)
= Σ
5
(I + h)22
k=
which allows for fast approximations of (xx at any precision. & can also be approximated by the reciprocals:
1
1
1 -- 1
+ 2x
(xx
(6)
x 23' which implies that v'(x) x 32 as x + O and d'(x) ~ as + 00.
x
2.4 Related work
There are several studies on the differential privacy of obtaining a single draw from a probability distribution whose probability density function is of the form y + {p()))))()). Here, x sensitive data, æ + p(xly) is a probability density function for all y in the domain, μ any positive-valued function, and Z is the normalizing constant. Wang et. al. (2015) showed that, when [log p(= y)1 B for some constant B, then a [logp(>
single draw is 4B- -B-differrnttially private. However, the densities that study are not bounded away from zero; they have the form II. s/ (i)))) which becomes small when one of the yt's is close to zero. ramiks lt al. (2017) showed that, when p is the density of the binomial distribution and μ is the density of the beta distribution, then single draw is 80,8)-DP, and the result cannot be improved unless the parameters are assumed to be above positive threshold. As a continuation of their work, prove in the appendix that, when the parameters are bounded below by a >> O, sampling from the Dirichlet distribution (which is a generalization of the beta distribution) is (e, ODDP with E > 0.
Let be sufficient statistic of an exponential family with finite el e'-sonsitivity, Foulds et al. (0116) showed that sampling Y ~ p(y | &). where = x + Laplace noise, is differentially private and as asymptotically efficient as sampling from p(y] z). However, for a small sample size, the posterior over the noisy statistics might be too far away from the actual postcrior. Bernstein Sheldon (2018) thus proposed to approximate the joint distribution p(y, x. ft) using Gibbs sampling, which is then integrated over æ to obtain more accurate posterior over G..
5

---

Published in Transactions on Machine Learning Research (02/2023)
Geumlek et al. 2017 were the first to study sampling from exponential families with Rényi differential privacy (RDP: Mironov (2017) Even though they provided general framework to find (A,e)-RDP guarantees for exponential families, explicit forms of Ả and the upper bound of A were not given.
The privacy of data synthesis via sampling from Multinomial(()) where Y is discrete distribution drawn from the Dirichlet posterior, was first studied by Machanavajihale et al. (2008). They showed that the data synthesis is (e,6)-DP, where é grows by the number of draws from Multinomial(y). In contrast, we show that a single draw from the Dirichlet posterior approximate DP, which by the post-processing property allows us sample from Multinomial(Y) as many times as we want while retaining the same privacy guarantee.
Gohari et al. (2021) have recently showed that the Dirichlet mechanism is (é(r, (.7,,, v/), 8(r, 7. m r/))- DP, where 7, "/ E (0, are additional parameters. Not only the guarantee has many parame- ters to optimize, it is also computational intensive. Specifically, for any W c [d], define 2 {p E Sd-1 Pi 7/ Vi W; Eiew 15-11t, Gohari et al. proposed é = O( (og((1)) and {Pr[Y, > vi E W] Dirichlet(rp)) 8=1- min
(7)
pEo"" WCl4
To compute 8, we have to approximate Pr[Y > 7] with numerical integration scheme with high precision, otherwise the integral may be greater than one. Even then, the integral is highly dependent on the scheme, and for some choices of the paramcters r, 77, : the value of 8 cannot go below a cerlain threshold. We illustrate this Figure 2 With r 171.87, 7) 0.028 and r/ 0.114, the value of 5 cannot go below 2.1 10-4, In contrast, compute, as the function e can be easily approximated via its series representation (equation 5j. Moreover, we are the first to provide the utility of the Dirichlet mechanism in terms of KL divergence minimization.
guarantec is much simpler to
Figure 2: A numerical simulation of 5
(equation 7 as a function of y.
3
Main privacy mechanism
3.1
The Dirichlet mechanism
Let X + Rd be an arbitrary vector-valued function with finite l2- and sssscnittissiiss: there exist two constants A2, A 0 such that
sup 2,2' neighboring
- 1 A3 and
sup 2. neighboring
[1(x)) - fxx') I Ao.
Algorithm 1 below details the Dirichlet mechanism used to privatize x E N...
Algorithm (A,e)-RDP Dirichlet mechanism
Input: A datasct æ XN, vector-valued function f NN RSo with e-sonsitivity A2 and go eecssiiittvt
A.c
Parameters: À 1, 0
Use a root-finding algorithm to find such that e 3 (1 +3A 1)).
2. Let a 1 4(A - 1)
3. Output y ~ Dirichlet + a))
The following lemma ensures that we can obtain an in Line I for any 0:
Lemma 2. With e, Ae > 0, Aox > 0 and x 2 1 held constant, the function r + 2 2rr 3(A 1)r defined on (0, oo) is strictly increasing from 0 to co. Consequently, the equation
8 _ Xr A3
(1 + - +((2-1)rAxx)
2
has unique solution in for any E, Az A. and X
The proof of Lemma 2 can be found in Appendix D

---

Published in Transactions on Machine Learning Research (02/2023)
À 2
À = 20
200
100
109
100
10-1
10-1
10-2
20
10
10-3
10-3
10-0
10-4
True E
True s
True
10-5
10-5
Algorithm
Algorithm
Algorithm
10-5
10-6
10-6
10
10
10-1
10a
10
10
10
109
10-
10
10
104
r
F
2
À
200
100
169
109
Uniform
Algorithm
Kl divergennce
20
KI. divergence
KL. divergence
8 x 10
Gohari et
Uniform Algorithm
Uniform Algorithm I Gohari et al
10
Gobari et al
10
3 10
10-3
10-1
10-2
100
10
10
10-2
10-3
100
10
10a
10
10
100
100
10a
Figure 3: Top: Plots of the Rényi divergence (e) between (irichlet(rf((x) + +a) and (irichlet (x'())))+())))))))))))) +o) using the direct calculations and Algorithm Das function of for À E (2,20, 20, 200) Here, f(x: (11, 8, 65, 25, 38, 1), [(x') (11,7, 7, 65, 25, 38, 0) and a = 1 + 401-4(()))))) - 1)r. Bottom: Plots of (xi(vvl/(xt)) for multiple instances of y drawn from Dirichlet(rf(at + a), where f(z) = (119, 74, 618, 272, 13, 187), a = 1 + 4(A - 1)r, and A e (2, 20, 200). For cach é, the privacy parameter r is chosen to satisfy (E, 1110-5-DPP according to (1) the results Gohari al. (2021) and (2) the conversion from our RDP guarantee to approximate DP.
3.2 Privacy guarantee
Theorem 1. Algorithm is (X,e)-RDP.
The proof of Theorem can be found in Appendix E A few remarks are in order.
replace ((1+3(A-11)AA in Line 1 by (1+++(r)) a 1+4(2-1)) in Line 2 by a= g(r) + (A - 1)rAxx for any function y R50 + Rzo. In particular, choosing v 2: (AA3)(() which can be computed without a root-finding algorithm. However, this choice of makes grows r², which becomes too large when > 1. Instead, we choose g(r) to be constant factor of an existing term (A-1)r in a, which allows us to offset the X factor in with v/((1 (()))((r) = o (TAAA-IF)
Remark 1. In general,
yields
Remark 2. If one has prior knowledge that fi(x) > b for some b b>0 0 for all x E V and all i E [d], then the proof of Theorem ! can be modified so that (A,E)-RDP can be obtained by setting r to be the solution to the equation& e & 2 AA + rb + 3(A - 1)). Since &f is strictly decreasing, this leads to a larger value compared to Algorithm
To demonstrate the lightness of the privacy guarantee of Algorithm | we simulate two neighboring histograms: f() = (11, 8, 65, 25, 38, 1) and f(=') = (11, 7, 65, 25, 38, 0). As functions of r, we compare a in Line [ with the analytic values of the Rényí divergence between Dirichlotrff(a)) + a) and Dirichlet(r) - + a), where a is given in Line 2 The plots of as functions of in Figure 3 show that our proposed @DP-guarantees are close to the actual Rényi divergences across different values of X.
7

---

Published in Transactions on Machine Learning Research (02/2023)
We also perform another simulation in order to compare our privacy guarantees with the ones from Gohari
et al. (2021) in terms of their effects on the KT. divergence. In this simulation, we apply the Dirichlet. mechanism with these privacy guarantees to the following count data: f(x) = (119, 74, 618, 272, 13, 187). For each À E {2, 20, 200), we define a = 11 + 4(A - 1)r as in Algorithm [ Since the results of Gohari et al. are stated terms of approximate DP, we have convert our result. from RDP to approximate DP (see Appendix B for more details on the conversion). For each ranging from 0.001 to 100, we use Theorem (with the conversion) and Gohari et al's results choose is (é, -DP.. We then draw multiple instances, say y, from the distribution and compute DKL DkL(f(z) (l) Finally, we plot the KL divergence as a function of é, as shown in Figure 3 As a bascline, we also plot the KL divergence between f(x) and the discrete uniform distribution. We can see that privacy guarantee generally provides smaller KL divergences than that of Gohari et al's. However, as À becomes very large, the algorithms outpul discrete probability distributions that are close to being uniform. The missing points in the À = 2 and À = 20 plots are related to a precision issue with the Gohari et al.'s method that we pointed out in Section 2.4 because of insufficient precision in numerical integration, we could not bring the value of
that single draw from (irichlet(r/(())+
down to 10-5
4 Utility
Let us recap the setting with which apply the Dirichlet mechanism: we have a sensitive dataset x E X and an arbitrary vector-valued function ʃ X + Rd Let N, == E; fi(x) and f(x) = (T) E Sd-1 We propose the Dirichlet mechanism (Algorithm 1 which aims to output y that minimizes DRL. (fx))ly while keeping x private. This motivates us to measure the utility of the Dirichlet mechanism in terms of the KL divergence between f(x) and To this end, we can make use of the following bound:
Theorem 2. For any > 0, (pI....,Pa) E S and q Dirichlet + a), the following inequality holds for any 1 > O and any B 2 de//2 1)):
Pr[DKL(pllq) n| S e Bn (22+m)(43m)
The proof can be found in Appendix F Since the Dirichlet mechanism outputs y Dirichlet(r + a) Dr + æ), we can apply Theorem with p f(x), y and B rNyy As long Ny 2 da/ (r(e7/2 - 1)), we have the bound
Pr DKL. ((+))l)) n| Nenn ((
We shall assume that 1 << and x 2. To obtain DKL (f())ly) 17 with high probability, one needs
do Ny (2 raj + p(en/- identities from Algorithm
Now, we would like to write r and a terms of e and using the following
8 - Xr A +3 1))
(8)
a a= 4(1 1)
(9)
We recall from Lemma that the rinht-hand side of equation g is strictly increasing function of from
0 to oo. This implies that, as - oc, we have
Under this limit, it follows from equation D that
61(1 + 3(A ( 1)rAa) = o (A--))) Thus, equation 8 and 9 give r r= O(E)) and O((A 1)s). On the other
hand, as if + O, we have r which implies s' (1 + 3(A 1)rAx)) O(1). Consequently, r ((Ve/A)
and (1)) Therefore, to attain the (), ERP guarantoe, needs
Ω
i 2
217
N₂
Ω
if < 1.
8

---

Published in Transactions on Machine Learning Research (02/2023)
The most common example is when the data is categorical, that is, [d] and f((x) is the number of i's in 2. Then Ny = Ji = N, and the analysis above implies that the sample complexity for (A,e)-RDP and sub-n KL. divergence, with À and yy fixed, is N = = + 1) if 2 1 and N = (+) if 1.
5
Experiments and discussions
5.1 Naive Bayes classification
We consider the Dirichlet mechanism for differentially private multinomial naive Bayes classification. Given dataset D= {(x10) y (0) i== we construct a model to classify labels y E [d] from discrete features 2.(() = (x) ,01,,..,, xxx) E II Nx. where Hy,... ......,2g Xx are finite sets. For j E [d], k E [K] and c E Xs we denote the class count by N₂ = Eis T(y j)- For the k-th feature, we denote the feature-class count. by No.. = - I(y(*) = j. 2 c). We can use the count data to estimate the class probabilities and the class-conditional feature probabilities:
Prly أ| = ,, = N,/N and Pr[æg cly = = 0 J.,N
(10)
The naïve Bayes model assumes that, conditioning on the label, the features are independent. As a result, the probability of y j conditioned on (z1...., can be computed as follows:
K
Pr(y = -jkm,,... . xx] ] x Prly 5]
II
Pr(px ccy- =j]
1=1
N
Nk
N₂
K
6%
To modify the model with the Dirichlet mechanism, we sample 1.,,..., ..) (Nrichlet(r(N No) a),
where and are chosen according to Algorithm [ (with A = and Ax = 1) to attain (A, / + ID-DPP Similarly, for each & E K and e E Ne, we sample (Bi....., (% ~ Dirichlet(r_ ... + ax)) where r and at are chosen attain (A,:/(K< 1)}-RDP well. We then release म.. instead of â. and 0 instead of 04. for all j. k and c, which leads to (A,E)-DDP by the basic composition (Lemma 1 and the parallel composition of RDP mechanisms
To benchmark the Dirichlet mechanism, we apply the Gaussian mechanism and the Laplace mechanism to the naïve Bayes model. Specifically, we replace N, and je in equation 10 by their noisy versions, namely N₂ N2 + zj and Ntk- Nt + zfe where =f: (O, X(K + 1)/e) for the Gaussian mechanism and Zy: ck ~ Laplace b), where is calculated using Mironov 2017 Corollary 2) to attain (X, for the Laplace mechanism.
In this experiment, the naïve Bayes models with differentially private mechanisms are used to classify UCI datasets (Dua & Grafl 2017) with diverse number of aataacceeaatriiuttee/eeee The details of the datasets are shown in Table !] For each dataset, we use 70-30 train-test split. Before fitting the models, numerical attributes are transformed into catogorical ones using quantile binning, where the number of bins is fixed at 10.
For all privacy mechanisms, fix x 5 and study their performances We also add the random guessing model, which is (A, OD- model, as the baseline. The classification performances, measured in cross-entropy (CE) loss and accuracy on the test sets, are shown in Figure 4 and 5 We can see that, on all dalasets, the test CE losses of the Dirichlet mechanism are substantially less than those of the Gaussian mechanism and Laplace mechanism; they are remarkably close to those of the non-private model on the CreditCard, GermanCredit, Bank and Adult datasots. This result should not be surprising, as the Dirichlet mechanism is the exponential mechanism that aims to minimize the KL divergence, and thus the cross-entropy between the normalized counts and the parameters.
increases from 1 to 10.
9

---

Published in Transactions on Machine Learning Research (02/2023)
Table 1 UCT datasets used in the experiment
Dataset
IInttances
Attributes
# Classes
Positive
Source
CreditCard
30000
23
2
22%
Yeh & hui Lien
2009
Thyroid
7200
21
3
Quinlan et al.
1986
Shopper
12330
17
2
15%
Sakar et al.
2018
Digit
5620
64
10
Garris et al.
T997
GermanCredit
1000
20
30%
Grömping
2019
Bank
41188
20
11%
Moro et al.
2014
Spam
4601
57
39%
Cranor & LaMacchia
1998
Adult
48842
13
24%
Kohavi
1996
CrediCCard
Thyroid
Shopper
Digit
Randoo
Random
Random Non-private Dirichlet
Random
Noe: private Dirichett
Now private Dircclltt
privale
Test CE loss
Gaussian Laplace
Test CE loss
Gaussian
Test CIE. loss
Ganstian Luplace
Test CE loss
Gaussian
Dürichlet
Laplace
Laplace
100
logio(e) GermanCredit
log10 (e)
1og (e)
log 10())(
Bank
Spam
Adult
Random
Random
Random
Random
Not--private
Non-private
Non-private
Non-peivate
Test CB loss
Glussian
Disichlet
Test CE less
Goussiun
Dinchlet
Test CT loss
Goussian
Dirichlet
Test CB loss
Gaussian
Dirichlet
Laplace
Laplace
Laplace
Laplace
t0*
10'
(o)
Logio(E)
logio(s)
logio(E)
Figure Test CE losses of the original and four s5, naive Bayes models on UCI datasets.
In terms of accuracy, there no clear winner among the three mechanisms; the Dirichlet mechanism performs well the other mechanisms in most cases. Specifically, it has higher accuracies than the Gaussian mechanism the Digit dataset for > 0.1, on the Adult dataset for 0.1, and the Bank dataset for all values of
The difference between the two metrics stem from the fact that the cross entropy loss is continuous function of the predicted probability, while the accuracy is result of applying hard threshold on the probability. Thus the accuracy does not distinguish between, for example, two instances, 2, x' with Pr(y = 1|x] = 0.1 and Priy = 1|x²| = 0.4, but the CE loss will suffer almost three times as much when the true label of compared to when the true label z' is 1. Thus a model with high accuracy can have relatively low CE loss when they are too confident their incorrect predictions.
All in all, neither metric is an end-all for measuring classification performance, and we should look at more than one metrics when fitting model. If one wants to publish naïve Bayes model under privacy constraint that performs well in both CE loss and accuracy, then the Dirichlet. mechanism is attractive option.
5.2 Parameter estimations of Bayesian networks
We use the Dirichlet mechanism for differentially private parameter estimations of discrete Bayesian networks. Consider dataset. D (z(O)) ) where z(() (x ,
(6)
I X and Xı. -1.-.. Ax are finite sets. We
10

---

Published in Transactions on Machine Learning Research (02/2023)
CreditCard
Thyroid
Shopper
Digit
0.00
Test accuracy
0.40
Test accuracy
0.300
Test accuracy
01.03
0.8
0.79
0:94
0.76
0.92
0.83
Random
Non-privare Dinchler Goussian Laplace
Noe-private Ditichlrr Gausian Laplace
0.82
Non-private Dirichlet Goussian Laplace
Test
0..
Non-privatee Dirichlet
Gaussian
Laplace
0.300
(o)
(0)
1o (E)
logio(e)
GermanCredii
Bank
Spam
Adult
Noc-ptivall Ditichler Ganssian Laplace
0.52
Test accurayy
0.70
Test accuracy
0. 0.000
Test accuracy
Test accuracy
0.51
0.40
0.75
0.907
0.50
Noe- privase Dinchlet
0.70
privaee Dirichlet Gunssian Luplace
private Diricllet
0.75
Gaussaan Liplace
0.885
0.65
Gaussiaa
Laplace
0:40
-2
-3
log1o
log10 (E)
logio
log1o(e)
Figure 5: Test accuracics of the original and four (5,c)-RDP naive Bayes models on 8 UCI datasots. Plots of the random guessing on some datasets are not shown as its accuracies are well below the other models'.
name the K variables by their index: I, Given a Bayesian network and [K], we denote the set of parents of k. that is, the set of direct causes of k by Pa(k). Let (.) ('P((k) = (xt )eePa(k) be observed values of Pa(k) and Xpa(s) IliE Xe be the product space of Pa(k:). Given j Nx and C XPa(k)); we denote No Σn Pa(K) = c) and No.. Em I(af") j. c). The log- likelihood of the parameters
g% = Pr|xx = 5 Pa((k) c] is given by:
LL(0)
Σ kE[K] cEXPatt)
Σ JE
N/. log of.
(11)
Using the first-derivative test, the maximum-likellhoon estimators of the Bayesian network are follow:
N je
0h
(12)
jc
NE
We can modify the model using the Dirichlet mechanism: assuming that X = [d], we replace (ot...... .hh by (@).:..., .%.c) ~ .N
+ a). Here, r and a are chosen according to Algorithm 1 to attain (A,e/K) -DDP. By the basic composition (Lemma and the parallel composition, releasing 0%. for all k E [K], E X and e E XPa(k) is (A,e)-DDP
We will compare the Dirichlet mechanism with the Gaussian and Laplace mechanisms. In equation 12 we replace N₁. by its noisy version: Je = Nr + Zee where 2,c ~ (K/s)//s) for the Gaussian mechanism and 2fe Laplace(O, b), where b is caleulated using Mironov (2017 Corollary 2) to attain (A.e/K)-RDP for the Laplace mechanism. In addition, we replace No by N =
N+ N,
In this experiment, we have prepared Bayesian networks on the Adult, Bank and GermanCredit datasets, which are parts of full networks provided by Le Quy et al. (2022). The Bayesian networks are shown in Figure 5 As in the previous experiment, we use a 70-30 train-lest split on each dataset, and continuous attributes are transformed into categorical attributes via quantile binning, with the number of bins fixed 10.
For all privacy mechanisms, we fix 5 and study their performances, in terms of the log- liceliils of the privatized parameters the test sets, as increases from 10-3 3 to 10. The plot of the ligeliielsoods
11

---

Published in Transactions on Machine Learning Research (02/2023)
Adult
Bank
GermanCredit
housing
peoperty
otber-debitrs
mucech
housing
pirrposo
ediacations
vricapation
pdays
pontoomme
Wimm credits
Gex-marital
installizent-n Fate
expital-gain
capital-loss
campaign
credit-hist
prople-libbl
duration
incouee
diaration
other-istaalivest
Foringn-worken
Figure 6: Our Bayesian networks on three datascts.
Adult
Bank
GermanCredit
1206
Test log seelikelihood
Test log- feg-likelifoood
Test log li---ieeehhodd
1900
Non-private
Non-private
Non-private
.398
Dirichlet
Dirichlet
-20A
Dirichlet
Gaussian
Gaussian
Gaussian
-1D0X
Laplace
Laplace
I Laplace
12591
-3
-3
[o)
log1o(=)
log
Figure Test log-likelihoods of the parameters obtained from the maximum--ikelihood estimation (non- private) and three (DD mechanisms.
as functions of e are shown in Figure 7 Dirichlet mechanism are substantially less than those of the Gaussian mechanism and Laplace mechanism for 1. The results agree with our suggestion to the Dirichlet mechanism for privacy-aware KL divergence minimization for discrete parameters, as it is equivalent to likelihood maximization.
We can see that, on all datasets, the test ligeliiel of the
6 Conclusion
The Dirichlet mechanism is an instance the exponential mechanism whose loss function is the discrete KL divergence -his motivates us to use the Dirichlet mechanism for private estimation an empirical distribution in KL divergence. As consequence, the Dirichlet mechanism can be used for private likelihood maximization and cross-entropy minimization. This work provides choice for the multiplicative factor and the prior that achieves desired (A,E)-RDP guarantee. To demonstrate its elficiency, we compare our mechanism with the Gaussian and Laplace mechanisms for differentially private naive Bayes classification, and as expected, the Dirichlet mechanism provides significantly lower cross-entropy losses on various datasets compared to the other two mechanisms. We also make a comparison between the mechanisms for maximum likelihood estimations for Bayesian networks. Our experiment on three datasets shows that the Dirichlet. mechanism provides significantly higher log- lieeliklssssss than the Gaussian and Laplace mechanisms.
As the KL divergence a fundamental measure information thoory, we envision that the Dirichlet mechanism would become essential for many privacy-focused infommation-thooretie models with discrete parameters.
12

---

Published in Transactions on Machine Learning Research (02/2023)
Broader Impact Statement
The Dirichlet mechanism does not provide privacy protection for free, but with cost of some aceuracy loss: the higher the privacy guarantee, the lower the accuracy of the privatized model compared to the original model. Any losses incurred from the inaccuracy must be taken into consideration before deploying the privatized model.
Acknowledgments
The author would like to thank the reviewers and the action editors for valuable comments and suggestions.
References
Martín Abadi, Andy Chu, Ian J. Goodfellow, H. Brendan McMahan, Nya Mironov, Kunal Talwar, and Li Zhang, Deep learning with differential privacy. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi (eds.), Proceedings of the 2016 ACM SIGSAC Conference Computer and Communications Security, Vienna, Austrio, October 24-28 2016, pp. 308 318, ACM, 2016. doi: 001144/2977700 49.7988188. URL https::///// httt:::://oo.or//00/// 1145/297674999911 2978818
Rohit Agrawal. Finile-Sample Concentration of the Multinomial in Relative Entropy. IEEE Transactions on Information Theory, 66(10):6297-63) October 2020. ISSN 1557-9654. doi: 10.1109 10.1109/TII.2000 201.0/11...000299113..4
Necdet Batir. Some new inequalities for gamma and polygamma functions. Research report collection, 7(3), 2004. URL https://vuir. wwwaiir.uueeee vu. wu..du..uu au/1500/
Garrett Bernstein and Daniel R. Sheldon. Differentially private bayesian inference for exponential families. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa- Bianchi, and Roman Garnett (eds.), Advonces in Newral Information Processing Systems 31: An- nual Conference Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 2934,,934, 2018. URL htttps:/prroeeedingg hwwpoceeddnng..nuuiiiieeee neurips wwwprripssccpppa//22/11 h0sh//ahh// 180106770BCCf44631111aaaaa288882 wwt.le--bbtttttttt.mm. html
Clément L. Canonne, Gautam Kamath, and Thomas Steinke. The discrete gaussian for differential privacy. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, December 6- 12, 2020, virtual, 2020. URL lnttps://proceedinggg html
doi: 10. 250322 URL Boatisscccppee/////aaaaaaaaaaaap
Lorrie Faith Cranor and Brian A. LaMacchia. Spam! Commun, ACM, 41( 83, aug 1998. ISSN 0001-0782. http://..//111111//..511 280336
Christos Dimitrakakis, Blaine Nelson, Zuhe Zhang, Aikaterini Mitrokotsa, and Benjamin I. P. Rubinstein. Differential privacy for bayesian inference through posterior sampling. J. Mach. Learn. Res., 18:11:1-11:39, 2017. URL http::/jmlr http://www..ggppppr.//eeem wwtp:/appprs/vv/11-22222 html
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http://arccivveiie...ii.
m
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., ((3-4):211-005 2014. doi: 10.1561/04000000042. URL https://doi..org org/10.....o 1561/ D400000042
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. Serge Vaudenay (ed.), Advances in Cryptology - EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28- June 1, 2006, Proceedings, volume 4004 of Lecture Notes in Computer Science, pp. 486 503. Springer, 2006a. doi: 10.1007/11761699, 29. http:::://oi...ggr/..ooeee
13

---

Published in Transactions on Machine Learning Research (02/2023)
Cynthia Dwork, Frank Mesherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In TCC, 2006b.
James R. Foulds, Joseph Geumlek, Max Welling, and Kamalika Chaudhuri. On the theory and practice of crivacy-preserving bayesian data analysis. In Alexander T. Thler and Dominik Janzing (eds.), Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence, UAI 2016, June 25-29, 2016, New York City, NY, USA. AUAI Press, 2016. URL http:// auai
pdf
Michael Garris, J Blue, Gerald Candela, Patrick Grother, Stanley Janet, and Charles Wilson. Nist form-based handprint recognition system, 1997-01-01 1997.
Joseph Geumlek, Shuang Song, and Kamalika Chaudhuri. Renyi differential privacy mechanisms for posterior sampling. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 5298, 2017. URL https: http::///pooccciig.nooeeee neurips pttpppppppppppppppo/////// p0/11 1asa7/6677aaaat8663cccccccc. Aba.:00t0--ttttttttbb... html
Parham Gohari, Bo Wu, Calvin Hawkins, Matthew T. Hale, and Ufuk Topeu. Differential privacy the unit simplex via the dirichlet mechanism. JEEE Trans. Inf. Forensics Secur., 16:2326-25 23400 2021. doi: 0..1009/TIFS..22133005
URL
1109/TIFS
Ulrike Grömping. South german credit data: Correcting widely used data set. Reports in mathematies, physics and chemistry, Department II, Beuth University of Applied Sciences Berlin, 4 2019.
Abdolhosscin Hoorfar and Mchdi Hassani. Incqualitics on the lambert w function and hyperpower function. J. Inequal. Pure and Appl. Malh, 9()) 9, 2008.
Ron Kohavi. Scaling up the accuracy of naive-bayes classifiers: A dccision-tree hybrid. In Proceedings of the Second International Conference on Knowledgee Discovery and Data Mining, KDD'96, pp. 212-207. AAAT Press, 1996.
Tai Le Quy, Arjun Roy, Vasileios Iosifidis, Wenbin Zhang, and Firini Ntoutsi. A survey on datasets for fairness-aware machine learning. WIREs Data Mining and Knowledge Discovery, 12(3):e1452, 2022. cacley.cco/// com ddo////b//b//1
doi: https://doi.ors 11110000//iwii/ 1452. URL attp:://aare..oonnnellbarrr wiley. 1002/wi 1002/widm. dm. 1452
Ashwin Machanavajjhala, Daniel Kifer, John M. Abowd, Johannes Gehrke, and Lars Vilhuber. Privacy: Theory meets practice on the map. In Gustavo Alonso, José A. Blakeley, and Arbee L. P. Chen (eds.), Proceedings of the 24th International Conference on Data Engineering, ICDE 2008, April 7-12, 2008, Cancún, Merico, pp. 277-286. IEEE Computer Society, 2008. doi: 10.1109/ICDE. 4497436. URL
https://doi.. orgo 10. 1 1109/ICDE.
ICDE. 2008, 4497436
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pp. 94-103. IEEE Computer Society, 2007. doi: 10. 10.1109/FOCS.2007.11 URL https
//doi.orge 10. 1109/FOCS. 2007
llya Mironov. Rényi differential privacy. In 30th IEEE Computer Securily Foundations Symposium, CSF 2017, Santa Barbara, CA, USA, August 21-25, 2017, pp. 263 275. IEEE Computer Society, 2017. doi: 10.1109/CC5 /CF////F/.. CSF.2017.111 21. URL https://doi.oorg/1... 1109//S1 .017..1
Sérgio Moro, Paulo Cortez, and Paulo Rita A data-driven approach to predict the success of bank telemarketing. Decision Support Systems, 62:22 31, June 2014. doi: n..1016/j.dss.2144.... URL
https://doi. 10. 1016/j dss 2014.
John Ross Quinlan, Paul J Compton, KA Horn, and Leslic Lazarus. Inductive knowledge acquisition: a case study. In Proceedings of the second Australian Conference on the Applications of Expert Systems, pp. 183 20-2004 1986.
14

---

Published in Transactions on Machine Learning Research (02/2023)
Alfréd Rényi. On measures of entropy and information. In Proceedings of the Fourth Berkeley Symposium Mathemalical Stalislies and Probabilily, Volume 1: Contributions to the Theory of Statistics. The Regents of the University of California, 1961.
C. Okan Sakar, S. Olcay Polat, Mete Katircioglu, and Yomi Kastro. Real-time prediction of online shoppers' purchasing intention using multilayer perceptron and LSTM recurrent neural networks. Newral Computing and Applications, (1810) May 2018. doi: 10.1007/s00521-018-- 10. 00010000800221-0--335----
URL https:///oi org/
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE Symposium on Securily and Privacy, SP 2017, San Jose, CA, USA, May 22-26, 2017, pp. 3 18. IEEE Computer Society, 2017. doi: 10.1109/SP:2017..11 URL https://doi.org org/ 10. 1109/SP 2017.41
Aki Vehtari, Andrew Gelman, and Jonah Gabry. Practical bayesian model evaluation using leave-one-out cross-validation and WAIC. Statistics and Computing, 27(5):1413-1432, August 2016. doi: 10.1007 s11222-016-9696- URL
Yu-Xiang Wang, Stephen E. Fienberg, and Alexander J. Smola. Privacy for free: Posterior sampling and stochastic gradient monte carlo. In Francis R. Bach and David M. Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, volume 37 of JMLR Workshop and Conference Proceedings, pp. 2493 2502. JMLR.org, 2015. URL manbceeedingsmm.r.... mlr.
http://prroceddings.
html
Jiayuan Ye, Aadyaa Maddi, Sasi Kumar Murakonda, Vincent Bindschaedler, and Reza Shokri. Enhanced membership inference attacks against machine learning models. In Heng Yin, Angelos Stavrou, Cas Cremers, and Flaine Shi (eds.), Proceedings of the 2022 ACM SIGSAC Conference Communications Security, CCS 2022, Los Angeles, CA, USA, November 7-11, 2022, pp. 3093 3106. ACM, URL htttp:://doi.orr/1...11ee 1ttp://...115535448888 3560675
Computer and
2022. doi: 10.1145 10.1145/35486066 (34455063356067777
I-Cheng Yeh and Che hui Lien. The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients. Expert Systems with Applications, 36(2):2473 2480, March 2009. doi: 10.1016/j.eswar 2007. URL https:///oii wttp::///oi.oo/1...111 1011// eswa. 2007 12.00.12.000
A Dirichlet posterior sampling is not e-differentiall private
We show that the Dirichlet postcrior sampling does not satisfy the original notion of differential privacy- the pure differential privacy.
Proposition 3. For any & > 0, the mechanism that outputs y (irichlet(rr((x) + a)) is not e e-differentially private.
Proof. Without loss of generality, let (0, 0,.., number. Let Dirichlet a) and y ~ (irichlet(rf(z') a). For any yo (81, .2...., ... ya) with Σg 81 1, we have
0) and x' (1, ...,)).))) Let be any positive
Pr(y yol Príy' yul
B(rs(x')+ + Lay B(rf(z)+ a
II v. +a(
B(rf(z')+a) B(r((z)+ +a)
91
For any 0, we can choose sufficiently small y1 0 that the right-hand side is larger than ef. 7
15

---

Published in Transactions on Machine Learning Research (02/2023)
10
100
90
À 2
À 10
1011
À 50
10
Figure 8: (s, 6)-D guarantees of the Dirichlet mechanism following equation
14 with A E {2, 10, 50, 200} and
10-5
B Approximate differential privacy
We convert from RDP to approximate DP with the following conversion formula:
Lemma (From RDP to Approximate DP [Canonne et al., 2020 Let E > O. If M is a (A,E)-RDP mechanism, then also satisfies (E, 8DP with
8 exp((A 1)(E - 8)) 1 ²
(13)
d-1
Taking the logarithm of equation
13
log = (A 1)(E= 6)) (A log( 1) AllggA);
which is equivalent to Plugging in the RDP guarantee in Algorithm
é = += - -1) log + A Aog(AA)
I we obtain
1 = A 2 (1 1)) + log(A - 11) log 5 + A log(A)
(14)
A-1
which gives formula for & in terms of À and 8. Figure S shows & as function of r at four different values of X. We can see that, at a fixed 8, é is increased when we increase r and decrease X.
C Experiments with approximate DP
We perform the same experiments those in Section 5 But this time, focus approximate DP instead of RDP, and we also include the Dirichlet mechanism with Gohari et al. (2021)' 's privacy guarantee in the experiments. Our RDDP guarantee of the Dirichlet mechanism is converted to (ε, 8)D guarantee, with 8 = 10-5, using the material in Section sec:adp. The results of the naïve Bayes and Bayesian network experiments are shown Figure and Figure 10 and those of the Bayesian networks are shown in Figure II
We highlight that our Dirichlet mechanism performs better than Gohari et al's in all experiments, and Gohari et al's mechanism performs significantly worse for smaller values of We also notice that, contrast to the results Section 5 the Laplace mechanism performs better than the Gaussian mechanism; this is because the composition property for multiple uses of an DP mechanism better than that of an (6, DDD for any > (see Dwork & Roth (2044 Theorem 3.20))
Aside from similar results as those in Section 5
16

---

Published in Transactions on Machine Learning Research (02/2023)
CreditCard
Thyroid
Shopper
Digit
Random
Kandom
Random
Random
Now peivate
grivate Dinchie
peiste
101
Drsciler
Dinehier
Test CE Joss
Litaan all Gamesan Laplace
Test CE loss
Gonan et
Test CE loss
Cithert
Test CE loss
Lebann et
Gzueetan Laplace
Carasson
Lapiico
(
log10
1og1o (
1og10((
GermanCredit
Bank
Spam
Adult
Non-private
Nun-privaee
Nenopriote
Non-privat
Dinchla
Dinihik
Deictlet
Dinchis
Test CB loss
Golsan
Test CE loss
Test CB loss
Test CB loss
Goban
Laplace
Laplas:
Laplazz
Eaplac:
22
-2
(E)
(ogio(E)
logio(E)
log 10(E)
Figure 9: Test CE losses of the original and five (E, 10.10-30 S-RDPP naïve Bayes models on UCI datasets.
CreditCard
Thyroid
Shopper
Digit
Rasdlon
Test aceuracs
Test accurdey
0.8
Test accuracy
0.7
Test accuracy
Disihher
Gubari
Consinn
0.85
Taplacs
geiuuee Duschlet
grivate Diriftee
Non
0.5
0.30
Gohari
Gaussion
Gaussian Laplace
Goluaii et
Gahadt
Garssiaa
0.40
Lapluce
Laptace
(og
(o)
logio (E)
logia(E)
GermanCredit
Bank
Sparn
Adult
0..8
Test accuracy
Test accuraccy
Test accuracy
Test accuracy
0.11
0.6
0.65
0.5
Non
0.60
Dinchter
Gchon
Gobann et
Dincheer
Dincher Gobun
0.55
Conhan
Dinchier
0.00
-1
-2
-2
-1
1oggo
log1o
1oggo
log.o
Figure 10: Test accuracies the original and five (E, 10-10-b0 -D- naive Bayes models on UCI datasets. Plots
of the random guessing on some datasets are not shown as its accuracies are well below the other models:.
17

---

Published in Transactions on Machine Learning Research (02/2023)
Adult
Bank
GermanCredit
1294
Test log likellhoodd
Test logg-llgiee lil--iihkhoodd
Test log likelihood
Non-private
Non-private
Non-private Dirichlet
Dirichlet
Dirichlet
Laece
Gohari el
Gohuri et al.
Gohari al.
Gaussian
<086
Gaussian
Gaussian
Laplace
Laplace
Laplace
logio
log1o (
log1o(6)
Figure 11: Test log- likelihoods of the parameters obtained from the maximum-likelihonn estimation (non- private) and four (é, 10 (6,10-5)-.0 9--DP mechanisms.
D Proof of Lemma 2
Denote 3(A 1)rA.c. With e, A2 and A.c fixed constants, write the equation as
C (3 (1 + 2) for some constant C >>> 0. From equation 6 we have vi + x) = 0 (1+2}²) as + 0 and
(x(x)) θ 1t
as Consequently,
lim 2 / + x1+ = and x-0
lim 21d (1++1) oc. 20000
(15)
The conclusion will follow we can show that the function first use (1+1+ < I+
((x) 2b v + x)) is strictly increasing. For this,
I
(1++)² to obtain
[1'(1 + x²) v +1++) v1(+xx)
21 +x)
2 21 +x)
1+
x1+ ++x x
x
In other words, 20 + x) > x c (1 + x)}2 Combining this with (2)) + v0 > 0 (see e.g. Lemmal.1)), we have
Batir 2004
6'(x) = 2xx/ (1 + +) + 2 / (1 + x) (b + x)} + w + =) x² (1)) + (x)) > 0.
15 implies that the equation xxx) has a unique solution zg for any & >> 0. We then obtain solution in r by letting r = xe/(33/// A 1)
Therefore, (xx) is strictly increasing, which, combined with equation
E Proof of Theorem 1
Case 1: >>
Let x and x' neighboring datasets, For notational convenience, let u rf(x) + a and rf((x') + a. As usual, we write (u,...., ua), u' (u/...., .,, u()), un == E, u, and u/ = Σ, u/z Let P(y) be the density of Dirichlet(u) and P'(v) be the density of Dirichlet(u'). To compute the Rényi divergence between P(y) and Pl P'(y), start with:
P(y)a-11 B(u')~-1
B(u)A-1 Ey-P(w) [yaa-)(a-a9]
E P(v)
B(ud)~1 B(u + (A - 1)(u - ='))
(16)
B(u)A-I
B(u)
where (mu) ("uo)--III is the multivariate beta function. Thus the ratio can be expressed in terms of gamma. functions:
B(w') T( ut) I(uo)
r(w))
II r(w))
B(u) Il.(())TT(E u)) r(u))
18

---

Published in Transactions on Machine Learning Research (02/2023)
where uy == - Us and 2/g == E, ut. Similarly,
B(u+ + (A - 1)(u u'))
r(E; uz) r( u4 + (1-1) Σ, (1 - u()
r(u; + (1 - 1)((s u())
B(u)
I(u;)
Taking the logarithm on both side of equation 16 we need to find an upper bound of:
P(y)A-11
log P(u)
P'(y)>-1 = [(G(u, u/) + H(u, x4)) G(uo, u6) H(uo, u6)).
(17)
where
G(u,, u() = (A (]og T(u)) - log I(u;))
H Huu, u!) = log I(u (A 1)(u, u()) - log (u.):
and similarly for G(uo, un) and Hug, uh)) Using the sccond-order Taylor expansion, there exists & between u, + (A 1)(u, - u4) and ui, and 5 between u, and ut such that
1 1)(4 - (''))' G(u,, u4/ = -Ax- - 1)(u - (us) +
-( - 1)((((z)= - 2
+ 2 1)(f(xx) - (((21))777((E
H(u;, ul) (A 1)(u; (() + ( 1) (E)
1 (A 1)²(f((z) f((')))
= - ()) f( (r +
2
We try to find an upper bound of both (E) and (g'). If f((x)> > fi(2'), then uf < u, <u; + () u4)) u4).
Thus both & and g' are bounded below by u/ 2 a. On the other hand, if f((x) & f(('), then us + (A 1)(44 a S us & u4. In this case, & and g' are bounded below by:
u + (A - 1)( - u/) = f((x) + - (A ()-((())( -r((()))))((()))))
2a (A-
Since v/ decreasing, both (E) and v5') are bounded above by v'(a - (A - 1))..)). Consequently,
1
G(u,, u/) + H(u, ut)
(A - (4 -
(A 1)r
2
2 A(1 - - 1)(((z)) - f(221)2) - () 10)
The same argument can be used to show that, there exist to and Eo such that:
G(ua, v/) Huuo v6) - (A ({--1)(u)) 1)(u ((6)) + 1 =a 1)2(uo v1))2)((En) 0.
Therefore, continuing from equation 17
Dx(P()))P(()) x
GG(u, u4) + [u,, v/)) - G(uo. v/)) - H (wo, 2/6)
1
Σ (G(u, ut) + H H(,, u())
<
Σ (fi(z:)) [(x1)) (a (A 1)rAm)
< 2
2 Vi(a - (A - 1)rAxx)
(18)
19

---

Published in Transactions on Machine Learning Research (02/2023)
Case 2: A 1.
We use the following formula for the KL divergence between two Dirichlet distributions:
DRL. DkI(((r)))P())) = log ((uo)
Σ log ((us) - log (1/))
Σ (uf) + E(,, -))((()))))))) ((u))),
From this, split the right-hand side into two parts and apply the Taylor approximation before:
Σ log ((ui) + Σ log [(u)) E (us ((s))))
S Σ [u - u()) (minfu,, uf})
Σ (ui v1)3
5 2
2 E(h(I:) - (((3))337001
/ 13
$
and
log [(uo) - log ((u))
Σ (uo v6))(1)))))))))))))))))))))))v
1 2
Σ (u: (mmxx v61)
5 0.
Adding these two inequalitios yiclds the same incquality as equation
18 with
1.
Thus, given any À 2 1, > 0 and any R>0 + Ryo: if we let be the solution of Ax (()) = and a = + g(r) + (A - A)r then the inequality above implies (x)) < e. We conclude that Algorithm by setting g(r) = 3(A - 1)
F
Proof of the Utility bound
We first note pair of inequalities for the digamma function, which hold for all 1
log x - 2 < (xx)) log
(19)
We start with the Chernoff bound: for any t S 3,
Pr(Dxu(Pllg) > nl s e
tE e-"
(pll))
- to
(ps/gr) tr:
tp
bn
Apc
Spi 1p-ta-1 dq
B(3p + a)
B(pp - tp, a
bn
P
tpL
B(3p a
I(3 + da)
spc 1(3p - tp: a
= = bn
II
(20)
I(B - t + da)
r(šp: +a)
20

---

Published in Transactions on Machine Learning Research (02/2023)
Using the first-order Taylor approximation, we have the following estimates for oog-gamma functions:
log [ + da) Σ log [ - - da) + tw + da) log (Bp; tp: + a:) log [gp: + da) tp. tp: + a).
Inserting these inequalities and equation 19
into equation 20
we oblain
(r(Pet(PPla) > n) S e Mn (V(+
Pi -pp
< < t da)
II p e tp, log(sp: popp(ppp-pptt--11
=e + do)'
II tP (3ps - lp; + a - 1/2) tp:
=0 + da
II (3 + P: (a 1/2)) tp.
3 + da
1pc
3 + Pi
(a 1 1/2)
B + da
by
B - 1
8 do:
bn
3-1
8 + do B - t
exp
-tm + tlog
exp(f(t)).
(21)
The function f(t) is minimized at t" = W that W satisfies the identity log(W(x))z))
Be--m
where W is the Lambert W function. Note
B+da
W Wxx) for all -e Therefore,
3 + da
+ log
B 1*
8 + da
Beltn
-t'n + log
WW
B
3 + do
3 + da
Beltn
-1'n + log
W
+ t" log l
Beltn
1+ dox
Bettn
-t'n - l'W
+t"(1 +1)
B + do
Bel+n
1-' 1 - W
33 - da
Beltn
-1
Be
- 1 - W
(W
(W
-1)
(22)
3 + da
B + da
21

---

Published in Transactions on Machine Learning Research (02/2023)
The assumption 3 2 da/(er/2 - 1) implies 3/(3 + da) > 6/9/ We use the incquality W(x) log
log log r + log log (0ggz((2)) (2) for x 2 Hoorfar & Hassani
2008
Theorem 2.7) to obtain
W Beltn B + do
2 W ( (elt/22)
!! 2
+ log(1 + m/2)
2 1
log 1
2
2(1 7/22)
1 1+11 17 +
log 1 + !!
1
+
2
2
7
17
1 1+1 1
2
1+
+ 2(2 11)
2
2
2
1
Continuing from equation 22 we have
f(t)) - 8 1 - 1
+
7
1
1) = -8
172
2(2 + 7))
2(2 17)
2(2 ()) + 3n)
Inserting this inequality back into equation
21
we obtain
Pr[DR((Plle) > n| s exp(f(t) s exp(f(f")) (6-00(22(+))4445
desired.
22


Reviews:
[{"review_id": "Sr43ucyr4g", "reviewer": "Reviewer_5JaD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- An efficient tight privacy analysis for the Dirichlet mechanism is a main contribution of this paper. The authors demonstrate the tightness of their bound by comparing it to a numerical computation of the Renyi divergence between the mechanism run on two neighboring databases (Figure 2). This figure is pretty convincing in highlighting the tightness of the result.\n- The experiments the authors perform show that the proposed algorithm outperforms Gaussian and Laplacian perturbation algorithms. These seem like a reasonable baseline, although it would be interesting to know if there are more reasonable algorithms to compare to (e.g. the exponential mechanism with a truncated KL divergence?)\n- Having the motivation for KL divergence minimization fleshed out more would have been helpful. The description of the applications/motivating examples was short. In particular, I am not very familiar with the “test CE Loss” vs. “test accuracy” discussion. The proposed algorithm is designed to minimize the test CE loss, and performs well at this task, but does comparably to the more naive algorithms for the test accuracy. I assume this is something inherent about these two metrics (not the algorithm) but further discussion would help motivate prioritizing the test CE loss. Figure 4 (bank) was particular confusing.\n- Although the algorithm proposed fits into the structure of the exponential mechanism, due to the infinite sensitivity of the KL divergence, it is not an instance of the exponential mechanism. Therefore, the privacy and utility proofs are not covered by the standard theorems. This is mentioned in the introduction but I thought further discussion was warranted to motivate the problem. For example, the proofs are quite different to those given in the standard theorems, and this seems worth pointing out. Similarly, further discussion of Geumlek et al. (2017) and Gohari et al. (2021) would help motivate the problem. In particular, a numerical analysis comparing to Gohari et al. would be useful to assess how this work improves over that work.\n- Although the results are interesting, the presentation of the results could use a lot of improvement. I thought that throughout the paper, the authors required a lot of the reader, skipping connecting sentences and background information that would greatly improve readability. I often found myself having to fill in information.\n- I did not find any errors in the proofs of the theorems.\n\nMinor Comments:\n- Places where more information would be useful. In many of these places just an extra sentence or two guiding the reader would substantially improve readability.\n    - The introduction of the problem at the bottom of page 1 needed more explanation. A simple statement stating that we were going to interpret the the count data as discrete pdfs would improve readability.\n    - Terms are often used without explanation (e.g. polygamma). These are standard terms, but it is helpful to include a definition since they form an important part of the theorem and proofs. \n    - I understand brevity is a priority in discussing related work but, without prior knowledge I would not have been able to follow some of the related work. E.g. when discussing Wang et al. 2015, the mechanism is only described as “probability sampling”, what is this?\n    - I found the discussion of the proof of Theorem 2 in the main body (pg 6-7) quite confusing. In particular, it was not clear to me why eps>=1 implied r>1 and phi’(1+2(lamb-1)rDelta)=Theta(1/(lambda-1)r)? Was this explained?\n    - In the applications section (5.1), more explanation would be helpful. The authors go straight into technical material and a reader unfamiliar with naive Bayes models would struggle to follow.\n    - A final line in the proof of Lemma 2 stating why the fact that phi(x) is increasing and limits towards 0 and infinity implies a unique solution for every eps would help the reader.\n- The third paragraph of the introduction oversimplified the vast research on differential privacy, claiming that many designs are simply output perturbation using Laplacian or Gaussian noise. The authors are aware of the exponential mechanism, which does not fall in this category. \n- On page 3, “In contrast to pure and approximate DP,…”. I don’t think “in contrast” is the right phrase here.\n- When introducing the exponential mechanism “beta is a privacy-related parameter” is a little vague, “function of epsilon” would be more clear.\n- On page 4 when discussing the bias, it should be clear that this bias is only over the randomness in the algorithm, not the population.\n- Typos: \n    - pg. 8 “in terms of accuracy, there are no clear winner”\n    - Pg. 10 “We study define”\n    - Mislabelled equation in the proof of Lemma 3?\n    - Psi’ is deceasing (not increasing) in appendix D.\n    - At end of appendix D, after “Therefore, continuing on from equation 12,”, x_i-x_i’ should be f_i(x)-f_i(x’).\n- I don’t think the “parent” relationship in a Bayesian network was ever defined. \n- I don’t think B or alpha_m were defined in appendix D\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose a version of the Dirichet mechanism that satisfies Renyi differential privacy. This algorithm privately outputs a distribution that is close in KL divergence to an empirical distribution. This makes it useful for naïve bayes classification and maximum likelihood estimation of Bayesian networks. \n\nWhile this algorithm looks like an application of the standard exponential mechanism from differential privacy (a non-obvious connection the authors establish), the privacy and utility statements are not covered by the standard results. The authors give privacy and utility bounds. The proof of privacy bounds in particular are different to the standard privacy proofs for the exponential mechanism in a non-trivial way.\n\nRDP guarantees for the Dirichlet mechanism have been studied in prior work, but the algorithm presented in this work is much more practical and efficient to implement.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Improve the prose, providing more background for the reader. Specific examples given in review above. \n- Discuss comparison with Gohari et al. (2021).", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "szp1JCDNa6", "reviewer": "Reviewer_XPY8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The solution is simple and intuitive, but to me it's not clear what this paper is trying to accomplish in the context of existing work. The proposed solution is essentially a mechanism for reporting histograms, and this is a well-studied problem in the literature on differential privacy. This paper seems to want to report (normalized) histograms with the goal of achieving good utility in terms of the KL divergence specifically. Why is this so important?\n\nNevertheless, let us assume that we care about reporting histograms with good KL utility. Then, I still think that there is not enough comparison to existing baselines. In the related work section, you mention the work of Gohari et al. What exactly are the similarities and differences between your work and this prior work? A thorough comparison is needed. It sounds like you're saying that the work of Gohari et al. involves some complications that your work avoids, but your mechanism is also arguably more complicated than the classical Laplace mechanism baseline. In the experimental section, you compare to the Gaussian and Laplace mechanism. How exactly did you arrive at the noise scaling for these mechanisms? The noise scaling looks loose. The experiments also confirm that the utility of the paper really lies in prioritizing KL divergence, because the proposed mechanism doesn't seem to fare well in terms of accuracy in Figure 4. Finally, you fix lambda = 5 throughout; I think you should show the comparison across different values of lambda.\n\nMinor:\n- At the botom of page 1, you have an example where you imagine a scenario that happens with probability 0 (noise is [-0.1,0.1]). That illustration doesn't sound convincing to me.\n- In the notation section, you say things like \"For any positive reals x and x′, the notation x \\propto x′ means x = Cx′ for some constant C > 0\". This doesn't compile. You're talking about functions/sequences, not positive real numbers.\n- At the top of page 4, you study the bias of y_i. It would also be interesting to look at the variance, because the variance should grow as alpha gets small.\n- At the beginning of the conclusion section, you have a typo (\"We study derive ...\").", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper discusses a Dirichlet mechanism for reporting a distribution computed on sensitive data, and the goal is for the privately reported distribution to be close to the true distribution in KL divergence. The solution is an application of the exponential mechanism and is shown to satisfy RDP.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "I feel that the paper needs significant improvements before publication, most notably a detailed comparison (in theory and experiments) to prior work on private reporting of histograms/distributions. When is the proposed mechanism better and in what sense? What is the best possible existing baseline? What is the comparison to Gohari et al.? How does the comparison change as you vary both epsilon and lambda?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Eou9ELh4hU", "reviewer": "Reviewer_a5Xg", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe main calculation made by the paper to convert the exponential mechanism to the Dirichlet mechanism is nice. The Dirichlet distribution is easy to sample from, and KL divergence is well-used, so this is a nice derivation.\n\nThe cross entropy loss for all the experiments is pretty promising.\n\nWeaknesses:\nThe cross entropy loss improvements don’t seem to translate to improved accuracy for the Naive Bayes models. It’s unclear exactly why this is, and there’s not any attempt to explain this.\n\nThe Dirichlet mechanism does not permit DP with delta=0, but the exponential mechanism is a mechanism which guarantees delta=0. It’s pretty unclear from the analysis in Section 2.2 where this gap shows up. It looks to me like this can be from the beta term, which should be the privacy parameter, being data dependent. This should be better explained, but fortunately the proof of Theorem 1 doesn’t seem to rely on this.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers the task of KL divergence minimization with differential privacy. They make the observation that KL divergence minimization with the exponential mechanism is almost equivalent to sampling from a Dirichlet distribution, with a mechanism they call the Dirichlet mechanism. They provide experimental results on Naive Bayes and Bayes networks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The only requested change that is critical to securing my recommendation is Weakness 2, and the following one:\n\nIt may be nice to plot the XE loss of random guessing as a horizontal line in Figure 3 (since label distribution and class imbalance vary between datasets). This would give a better sense for which epsilon values give meaningful results. This would also be nice in Figure 4.\n\nThe following would be nice-to-have things to address (in addition to weakness 1):\n\nTheorem 1 proof is deferred to Appendix D, but it’s labeled Theorem 2 there. This would be nice to be consistent, and it would also be nice to restate theorems before they are proven in the Appendix.\n\nIs it possible to have a lambda=1 result for Renyi DP?\n\nIt seems the privacy analysis requires r to be an exact root, is there any tolerance for numerical instabilities or other reasons a root-finding algorithm may return imprecise results?", "broader_impact_concerns": "I think the broader impact section is adequate.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Overall, the reviewers felt this was a solid and sound piece of work. The only remaining critique was from XPY8, who was unclear about the application/motivation of the given work, since it focuses on estimating the empirical distribution, rather than the population itself. The authors replied to this, sketching an argument about how it may imply things for the population setting (https://openreview.net/forum?id=lmr2WwlaFc&noteId=diapYqyugI). The authors are requested to add discussion and clarification to the paper on the distinction between the empirical and population settings, and whether results hold for which settings. For more on the population setting, some references the authors could consult include https://proceedings.mlr.press/v40/Kamath15.html and https://arxiv.org/abs/2302.06869.
Decision: Accept (poster)