Exactly Minimax-Optimal Locally Differentially Private Sampling
Authors: Hyun-Young Park
Shahab Asoodeh
Si-Hyeon Lee
Venue: NeurIPS 2024 poster (2024)
Keywords: Local differential privacy
Sampling
Privacy-utility trade-off
Primary area: privacy

Abstract: The sampling problem under local differential privacy has recently been studied with potential applications to generative models, but a fundamental analysis of its privacy-utility trade-off (PUT) remains incomplete. In this work, we define the fundamental PUT of private sampling in the minimax sense, using the $f$-divergence between original and sampling distributions as the utility measure. We characterize the exact PUT for both finite and continuous data spaces under some mild conditions on the data distributions, and  propose sampling mechanisms that are universally optimal for all $f$-divergences. Our numerical experiments demonstrate the superiority of our mechanisms over baselines, in terms of theoretical utilities for finite data space and of empirical utilities for continuous data space.

Exactly Minimax-Optimal Locally Differentially Private Sampling
Hyun- Young Park School of Electrical Engineering
Shahab Asoodeh
Department of Computing and Software
KAIST phy8118kaist.acckrr
McMaster University
asoodeh@mcmaster.. ca
Si-Hyeon Lee
School Electrical Engincering KAIST sihyeon@kaist.com kc
Abstract
The sampling problem under local differential privacy has recently been studied with potential applications to generative models, but fundamental analysis its privacy-utility trade-off (PUT) remains incomplete. In this work, we define the fundamental PUT of private sampling in the minimax sense, using the f- divergence between original and sampling distributions the utility measure. We characterize the exact PUT for both finite and continuous data spaces under some mild conditions the data distributions, and propose sampling mechanisms that are universally optimal for all f-divergences. Our numerical experiments demonstrate the superiority of mechanisms over baselines, in terms of theoretical utilities for finite data space and of empirical utilities for continuous data space.
Introduction
Privacy leakage is a pressing concern in the realm of machine learning (ML), spurring extensive research into privacy protection techniques [.H]) Among these, local differential privacy (LDP) 5 stands out as standard model and has been deployed in industry, e.g., by Google 71. Apple S
Microsoft [9]. In the LDP framework, individual clients randomize their data their own devices and send it to a potentially untrusted aggregator for analysis, thus preventing the user data from being inferred. However, this perturbation inherently diminishes data utility. Consequently, the central challenge in privacy mechanism design lies in optimizing utility while preserving the desired level of privacy protection. This goal involves characterizing the optimal balance between privacy parameter and utility, referred to as the privacy-utility trade-off (PUT). The analysis of the PUT and the proposal of privacy mechanisms have been actively conducted for various settings of statistical inference and machine learning 27
Most research in this field focuses scenarios where each client has only single data point. However, there are increasingly more applications where each client has large local dataset with
multiple data records. One formulate the privacy requirement in these cases by assuming that clients have datasets of the same size, generated independently from an underlying distribution (28)
34
This probabilistic assumption, however, restricts practical flexibility. The work [55] explored scenario where clients have large datasets that may vary in size and seek to privately release another dataset that closely resembles their original dataset. In this scenario, local datasets can be represented by an empirical distribution, allowing each client to be seen as holding a probability distribution and
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Original dist.
Sampling dist. [35]
Sampling dist. (ours)
2
-2
-2
Figure 1: Original Gaussian ring distribution and the sampling distributions of the baseline [3] and our proposed mechanism for privacy budget = 0.5. The implementation details are in Appendix
generating private sample from it. This setup, which is called private sumpling, is the main focus of this paper.
Private sampling has recently found applications in the private fine-tuning of large language mod- els (36). Additionally, private sampling connected the challenge of learning private generative models, topic often explored in the central DP model [37 While there exist studies on pri- vate generative models within the local model per client. Very recently, the work [49] considered setup where each client holds probability distribution, but in a different context of query estimation.
48 all these works assume a single data point
The private sampling mechanism in 335 can be described as follows. Initially, given probability distribution P representing local dataset, the mechanism assumes fixed reference distribution. then constructs what is termed the "relative mollifier", a closed ball centered around the reference distribution with a radius equivalent to half of the privacy budget, within the space of probability distributions. Subsequently, the mechanism computes the projection of /' onto the relative mollifier, utilizing the Kullback-Leibler (KL) divergence. This projected distribution serves the sampling distribution for generating sample (see Section 2.3 for more details). However, this mechanism has a notable shortcoming: the sampling distribution only locally optimal within the relative mollifier. This, in turn, implies that the optimality of the sampling distribution depends on the choice of the reference distribution. more fundamentally intriguing goal would be formulate and characterize the PUT without such an ambiguity in the choice of reference distribution.
In this paper, we establish the optimality of locally private sampling in the minimax sense, and identify optimal private samplers. Our primary contributions are summarized as follows:
The fundamental PUT of private sampling is rigorously defined in terms of minimax utility, which is commonly used in the literature of private estimation [T0] TT [3] (0). We impose some minimal assumptions on client's distributions in (38 (which studies sampling under central DP, a weaker privacy model than the local model (50)). For utility measure, we use the f-divergence [ST] [2 between the original and the sampling distributions, that includes KI. divergence, total variation distance, squared Hellinger distance, and x2 -divergence as special cases.
We characterize the exact PUT for both finite and continuous data spaces, and present optimal sampling mechanisms achieving the PUT. Surprisingly, our mechanisms are universally optimal under any choice of of f-divergence for utility measure.
We numerically demonstrate that our proposed mechanism outperforms the baseline method presented in [35) Specifically, for finite data spaces, derive closed-form expression for the utility of both our mechanism and the baseline, allowing for an exact comparison of their utilities. In the case of continuous data spaces, closed-form expression for the baseline is not available, so we use empirical utility for the comparison. Figure iillustrates our proposed mechanism outputs distribution closer to the original, than the baseline.
All codes for experiments and figures are attached as a supplementary material, and can be found at the online repository The instructions to reproduce the results in the paper are in Appendix H
http:://ggtabbb.cca/yysss//////p

---

2 Problem Formulation
2.1 Notations and preliminaries
Notations. For a sample space X, let P(2) be the set of all probability distributions on X. For each n E N, let C(TR*) be the set of all continuous probability distributions R For each positive integer & E N. let [k] == {1,2, ... .). For a subset A C X, A : X' 7 {0. } denotes the indicator function, defined [x(x)
for x E A and [z(z) and x E IR, let clip(2; 81, 82) == [sx m (52, 2}}} J. We refer to Appendix for the rigorous measure- theoreec assumptions underlying the paper.
for x & A. Also, for s1 S s2
f-divergence. For a convex function f (0, x)) - IR satisfying [(1) = 0 and two probability
distributions P.Q E P(() on the same sample space X, let D, (PIIQ) denote the f-divergence
[51 (2). The general definition of f-divergence is given in Appendix [ For X' = R2 and P, Q E
C(RR) with p << Q (that is, P(A) 0 whenever Q(A) 0), it defined as
S Jmm(())>
p(x) ((x)
Dy (PIIQ) =
{())
dr,
where p. 9 are pdfs of P. P.Q, respectively. and we define f(0) lim f(x) E (-o0, 20). For finite X, we can replace the integral with the sum and replace p, 4 with P, Q. Several well-known distance measures between distributions are examples of f-divergence with different convex functions. For instance, KI. divergence (relative entropy), total variation distance, squared Hellinger distance, and x² divdeeegge are f-divergences with fx) = x log f(x) = I 11/2, f(x) = (1 - vz)?.
and f(x) = x²² - 1. respectively. Two important properties of general f-divergence are keys for this work. First, D (PI Q) 2 0, and equality holds if P = Q. Furthermore, we have
Dy (PII)) S My = lim f(x) =f(//2),
(2)
x-0+
where equality holds if P and Q are mutually singular (that is, they have disjoint supports). For a more comprehensive list of such f-divergences and their properties, refer the readers to [52]
We denote the KL divergence and the total variation distance as DKI. (PlIQ) and Drv (P.Q),
respectively. We note that the total variation distance is in fact metric on P(2).
2.2 System model
Suppose client has access to distribution P E P(X') over sample space X, and wants to produce a sample in X' which looks like being drawn from P and to send it to a data curator. We assume that there are some constraints on the possible data distribution P, that P is restricted to be in some subset P C P(x), and both the client and the curator know X' and P. However, it is required that sampled element does not leak the privacy about the original distribution P. For this purpose, the client and the curator agree private sampling mechanism Q, which is conditional distribution from P to X. After that, the client produces a sample following the distribution Q(-lP). To guarantee the privacy protection, we impose Q to satisfy the local differential privacy (LDP) 10 35).
Definition 2.1. Let c > O. A private sampling mechanism Q is said to satisfy cLDDP, or Q is an c-LDP mechanism, if for any P. P' E P and A C X, we have
Q(A(P) S e' QAAPP))..
(3)
For convenience, for each PEP: P. let Q(P) E P(x)) denote the distribution of X given P through Q, that is (A) = Q(A(P) for each C X. In this way, we equivalently see Q as a function Q P + P()). Let 2x, denote the set of all e-IDP mechanisms Q P - P(2').
As the utility loss of the private sampling, we use the f-divergence between the original distribution and the sampling distribution, D, (PI)Q(P)) Since the sampling procedure can be performed across many clients who may have different data distributions, we measure the utility loss of Q by the worst-case /diveegeence.
(² sup Dy (PI)Q(P)) PEP
3

---

Given X, P. and f, our goal is to find the smallest possible worst-case f-divergence,
R(X,P, P.
inf
(Q(Q),
(5)
and to find mechanism Q E 2x achieving it. We say that Q E Qx is optimal for (X, under D, if ( R(x, P. f).
2.3 Related work
The most closely related work to our work
The system models are the same as this paper, except the formulation of PUT. They first fix reference probability distribution Qo P(X), and only
35
consider mechanisms Q satisfying e < Q(A(P) (*)2Qo(A) for all P P and A X. In other words, let Mc..0 Then, they only consider Q such that Q(P) E M..q.. Note that this guarantees e-LDP. For each P E P. they sought to find Q E Mr.Q which minimizes DKL. (PIIQ), and set this Q to be Q(P). First, they claimed to find a closed-form expression of such minimizer Q for finite X. given by
{Q P(X) : (o(() S Q(A) S (A))) AA C X).
(x)) clip (P(#)/rp;e 1/2 (o(x)) e Q0(x))
(6)
where rp >> O is constant depending P ensuring Exex Q(x) 1. Second, they presented an algorithm, called Mollified Boosted Density Estimation (MBDE), to approximate the optimal solution for continuous X. However, the utility varies over the choice of reference distribution Qo. and they left the question of choosing a best Qo to achieve the best performance in both practice and theory. Moreover, found that the closed-form in (6) is incomplete, because for some (P, Qo). there may be no rp > 0 such that the RHS of (6) does not sum to one. As an example, when P, Qo are point masses at different points, then we can easily see that the sum of (6) is </2 for any rp > 0.
Main Results
3.1 Optimal private sampling over finite space
First, we consider the finite case, where X' [A]] for some k E N. A natural setup for P is that P P(k)), i.c. there is no restriction the client distribution P P([k]). In this case, completely characterize the optimal worst-case f-divergence R(X, P,e, e, f') and find optimal private sampling mechanism. Surprisingly, for each k E N and > 0, we found a single mechanism which is universally optimal for every f-divergence.
Theorem 3.1. For each & E N, O, and an f-divergence D,, we have
e²
6* ce' 15=k-1)
1-1
R(K,,, ((K)),)) e² + 1
c - f(0).
Moreover, the mechanism Qi constructed as below satisfies e-LDP and is optimal for (X = [k), P P((k))) e) under any Dy:
(x((( = max P(x))
Va [k], P((A))
TP
where > 0 is a constant depending on P so that Σ (x) 1. Furthermore, Tp can be chosen such that I Erp S (e + k- (k-11)/a 1)/e*.
By definition, we have Qi Px 2 - for all x E X. This also implies that (x) k-
1 Er'ey(o) (x') P) < c i+ Hence, बमा < (x(P) I c
This clearly implies that Qi. satisfies c-DP..
Behaviors of the optimal mechanism. Let us observe some behaviors of the proposed mechanism with respect the system parameters, whose formal proofs are in Appendix E We visualize how the mechanism Q works for different in Figure 2 Here, write R to mean P(IK),,

---

for simplicity. If f(0) - oc, then R = oc, which means that R2 = oc for any e-LDP sampling mechanism Q. (Such a phenomenon happens for general (X, P), whenever P contains two mutually singular distributions) Hence, from now on in this paragraph, we assume f(0) < oc. We can observe that R is decreasing in and increasing in k. For a fixed k, we have R + 0
oc, which makes
sense since c - oo corresponds to the non non-private case. Also, as c - O, we have Q (x + 1/k for every P E PP(I)) and x E [k]. that is, Q (P) tends to the uniform distribution over [K] for every P E P(E)). This fact can be also observed by Figure
Remarks about the constant rp. The value of rp may not be unique, but the mecha- nism Q does not depend on the choice of rp. To see this, let us fix P, and let Suppose that Ex=1 (x) Ez=1 gr) 1 for S r'. Since (x( 2 gr for each I E [k]. the equality Σ (z(2)) Σx= (z) implies
Orgiiaa pmf P(r)
()(riP) 0.5 48 (),
Q1P c-
(x(x)) = max (P(())=4k-
Panlabxlity
that gr = 9r (2) for all x E kk.. Hence 9%
uniquely determined. Since r + Σt= (r()) is non-increasing and continuous, we can use the bisection method to find rp. The FFurther- more' part of the theorem statement precisely means that for r = 1 and r = (e + k 1)/e", the value of Σx= (-(x)) is at least and at most Figure 2: A visualization of the mechanism Q 1, respectively, 50 that we can perform the bisection method with these two initial endpoints to find r such that Σr= Gr (x) = 1.
2
3
valuae
Comparison with the previous work (35 The expression of the optimal mechanism in (8) is similar to (6). the expression of the KL divergence projection onto Me.Qo derived by Husain
et al. 135 Since c-+k-1 S Oi (x S -+ we can alternatively write (x =
P(x); w ( Hence, our optimal mechanism can be viewed as instance of a generalized version of (6). where Qo is a positive measure, not necessarily a probability measure e²/2 summing one, given by Qo(x)) = - A natural question is whether Q (P) is a projection of P onto MM.Qu. that is Qi (P) is minimizer of DKL (PIIQ) among Q E .M.Q... where Me.q. is similarly defined in Section 2.3] As we shall discuss in Section 3.3 this statement is true quite surprisingly- even when we replace DKL. with any other f-divergences. However, our analysis is more involved, as we need show the optimality of the proposed mechanism over any other possible mechanisms, including minimizers with respect to other choices of Qn- Also, in Section 5, we compare the worst-case f-divergence of our optimal mechanism with that of the mechanism proposed in 355 which restricts Qo to be a probability distribution.
clip Pp
3.2 Optimal private sampling over continuous space
Next, we consider the continuous case, where X' = In for some n E N. Some of the natural setups for P are (i) P = P(R"), (ii) P = C(R"). We can also think some restrictive but still reasonable setups, such as the setups where (iii) P is the set of empirical distributions supported on some non-empty open subset of IR". where (iv) P is the set of continuous distributions on []1, having smooth pdf and zero mean. However, we show that for general class of P including these four cases, any e-LDP sampling mechanisms have the worst-case f-divergence equal to the maximum value Mf of the f-divergence defined in (2) In the following proposition, X' may be general sample space, not necessarily R." or finite space. The proof is in Appendix [
Proposition 3.2. Suppose that P. contains infinitely many distributions which are pairwise mutually singular. Then, for any e >> O. for any c-LDP mechanism Q E Qx and for any f-divergence, we have (Q)= M,, where M3 is define at (
5

---

Hence, we need to consider sufficiently regular but practical setups for P.
Our setup. In this subsection, when P.Q E C(RR), the corresponding small letters p. q denote their pdfs. In this paper, we consider the case that
(9) and C2 c1 2 0. Some of the sampling tasks and generative models in literature [3 351 assume that the set of possible data distributions P satisfies P C Per.ez.h for some C1, c2, satisfying the aforementioned condition, hence (9) is a moderate assumption. One example is the sampling from Gaussian mixture, which is one of the canonical sampling tasks in literature [53] 35]. Suppose that P consists of Gaussian mixtures, where each Gaussian has mean within a unit ball centered at the origin and has unit covariance. That is. P = &E X In) k E N, 2 0, A = 1, l|plll S 1}, where In is the identity matrix of size X In this case, we can observe that P C Po,1, for h(x) (2m)-n/2 exp(- exp(-(maxx(,, ||=||| /)) and it can be easily shown that fg h(x) < oc.
P=Pa = {P C(R") c(((2) S p(x) S c2h(x), e R")
for some pre-known h X - [0, oo) such that fz. (h(r)dz
Without loss of generality, we may assume the following normalization condition on 01, C2 h.h
f h(z)dz= = ci <<<<o C2 > cIe'
(10)
The reason as follows. First, if any one of three inequalities Sa. h(x)dx > 0, 01 Sax h(r)dr < 1, and 02 Ja- h(x)dæ > 1 is not satisfied, then Poy, is either an empty set a singleton that consists of distribution having pdf e₂ ((x) or czh(z). which makes the problem trivial. Hence we impose all of the three inequalities. Then, we can normalize C1 C22 h, to make fg.. h(x)dr Furthermore, if C2 S e'c,, then for any P1 E Pon, we have P1 (x) S c2/c S e hence we can easily observe that the mechanism Q defined as Q(P) P for all P E P Per.eah satisfies hence the problem also becomes trivial, giving R(K", Por O.
and e 1 < oz.
e-LDP and (Q) Hence, we may assume 10).
Minimax utility and optimal mechanism. For the aforementioned setup, characterize R(X, P, e, f) and find mechanism which is universally optimal for every f-divergence. The formula is similar to the discrete case, with a carefully chosen clipping bound.
completely
Theorem 3.3. For each 02 C1 2 0, O, and h R" - 10, oo) satisfying the normalization condition (10). let us define the following constants determined by c1, c2, E:
C2 C1
b
(ee
())=
+2- T1 b
12
ber
(11)
Then, we have
f(2)) 1 1-r 1-ri f(r2)
T2 1
R(R", P Perceshe E, f)
T2 - T1 f(r)).
(12)
T2 -
Moreover, the mechanism Ve, constructed below satisfies e-IP) and is optimal for (X R", P Per.cch E) under any Dj:
For each PE Ro (P) =: Q is defined as continuous distribution with pdf
(_ bh(x),, be be=))())))))))())))))
q(x) = clip
(13)
TP
where rp > 0 is constant depending on P so that Sg g(x)dr = 1. Furthermore, Tp can be chosen such that Fı < Tp S r2.
It is also clear that Q hh, satisfies e-LDP. Also, we note that < < 1 < ber < C2 and 0 S r < < T2, which is shown during the proof of Theorem 3.3 in Appendix C
In practical scenario, it may be hard to expect P Pel.cu.h exactly, and we may only know P c Per,o,.h for some c1, C2, h satisfying aforementioned conditions. In such case, we still propose to use Q and in Section 5| we numerically show that this proposed mechanism is better than previously proposed mechanism 35) in terms of the worst-case f-divergence.

---

Behavior of the optimal mechanism. We also observe some behaviors of the proposed mechanism with respect to the system parameters, whose formal proofs are in Appendix Again. we write R to
mean R (IR.", , ,e. ; c, f) for simplicity. For fixed (c1, 02), is decreasing in c. 0j = 0 (which implies r1 = 0) and f f0) co, then R = oc, which means R2(Q) = oo for any c-LDP sampling mechanism Q. For the behavior at c + oo for a fixed (c1, c2), if c1 > O, then for sufficiently large we have Ciéº 2 c2 we fall in the aforementioned trivial case that R 0. If ci 0 and f(0) < xc, then as e + oc, we have R + O, which again corresponds to the non non-private case.
Remarks on the constant 7p- By the same reason as in the finite space case, the value of rp may not be unique, but Q¹ Le.. does not depend on the choice of rp, and Tp can be found by the bisection method with numerical integration of (3). Note that the continuity of r - I gr (z))dz; 9r (x) = clip (fp(x);; bh(x), be h(x)). follows from the dominated convergence theorem [4] since we assume fp- h(x)dæ < 00. The meaning of 'Furthermore' part is also similar to the finite space case, that is, the value of f (x))r at r = r1 and r = r2 is at least and at most 1, respectively,
that we can perform the bisection method with initial endpoints (21, (When r = 0, we define Or (x) = be h(x) whenever p(x) > 0 and gr (x) = (x) whenever p(x) = 0). A corner case is that when r1- 0, the continuity of r + f gr (z)dr does not suffice to guarantee the existence of strictly positive such that f (x))drr 1. However, in the proof, we actually show that Dr, (r))dr= 1 implies fg((d) 1 for every E (r1, which especially implies that even when = 0. there is a strictly positive r such that f (x)dr = 1. This is the reason that we state the strict inequality r1 < rp.
3.3 Proof sketch of the theorems
The full proofs of the main theorems, Theorems 3.1 and 3.3 are presented in Appendix C In Appendix C we present generalized theorem which includes Theorems 3.1 and [3.3 as special cases, where X' can be general sample space and P is similarly defined as in the continuous space case. The key idea for proofs and proposed mechanisms is to focus on the behavior of Q(P) when P is in an extreme case in P. In finite space, point masses are extreme cases, and for continuous space with p = =P -Peg.gghh the cases that p(æ) E (c))(()), { for all x E X are the extreme cases. As implied by the proof, the worst-case f-divergence of the proposed optimal mechanism is attained when P is in the aforementioned extreme cases. Such an approach using extreme case is a frequently used technique in PUT analysis (55)58).
Our proof consists of two parts, the achievability part and the converse part. The achievability part is to show that the worst-case f-divergence Ry (Q*) of our proposed mechanism Q is upper-bounded by the RHS of ( or (12). The converse part is to show that R (Q) of any e-LDP mechanism Q is bounded by the RHS of (7) or (12) From now, we briefly describe the proof idea of each part. Here, we omit the subscripts (k,,) or (ci, 02 h,,) e) for notational convenience.
PP Achievability part. Let 10MM=(Q'PP (P) Pe PJ. For finite space, M consists of all distributions
1 Q E P((k]) such that e-+k-1 S Qxx) S c for every x E [k]. For continuous space, M consists of all continuous distributions Q E C(R") whose pdf y satisfies bl(x)) S g(x) S be he (x) for every R".
We construct a mechanism Q such that Ry(Q²) upper-bounded by the RHS of 7 or The construction is as follows. First, we set a reference distribution μ E P(x') and constant Y E [0, 1] according to a certain rule specified in Appendix C Then, for each given P, we generate a private sample by sampling from the original P with probability 7, and sampling from the reference distribution μ with probability 7 In other words, we have (P) = >P (1 - 7)),. Our choice of μ and y makes (P)) e .M for every P E P, which especially implies that Q' also satisfies e-LDP, Furthermore, we can find a bound on the ratio of the pmf or pdf for original distribution to that for sampling distribution. Then, invoking [59 Theorem 2.1]. which bounds f-divergences given bounds on the ratio between pmf pdfs, we show that R (Q) is upper-bounded by the RHS of or
Next, we demonstrate a non-trivial generalization of the main result of [35] that Q*(P) is the f f-divergence projection of P onto M for P E P and every f f-divergence.
7

---

Proposition 3.4. Assuming the setups of (X, (X,P,e) )) in either Theorem 3.1 or 3.3 let Q denote the proposed mechanism Qe or he..e Also, let M be described above. Then, for every P E P and every f-divergence D,, we have Dj (PIIQ*
= infqem Dj (PIIQ).
Notice that this proposition differs from 35 in that it holds for all general f-divergences (as opposed to only KL divergence) and general sample spaces, be it discrete or continuous. This result immediately yields Dy (PI)Q* (P)) - D, Qi and hence (Q")") S R2(Q!) S (RHS of (7) or (12)) We remark that combining with the converse part (to be described below), implies that the Q is also optimal in minimax sense. Nevertheless, Q" outperforms Qf in that D2 (P)) for every PeP P.
Dj Q'
Remark 3.5. For the finite case, ju is the uniform distribution over [4: and y is taken in such way that Q! satisfies e-LDP tightly. In this case, an alternative way to implement Q' is as follows. For each given P. first we sample from P get raw sample and then apply the k-ary randomized response [60] to it.
Converse part. For each extreme P. let Ap be the "high probability set", defined as Ap = {or E X: P(z) = for finite space and Ap {a E X p(z) c2h(z)) for continuous space. Then, using the data processing inequality of f-divergence [61] we take lower bound of D, (P ((())) by the f-divergence between the distributions of A. (X) for X P and that for X ~ (P). Such a lower bound becomes decreasing function of Q Apl P) in a certain range. Then, we seek to find an upper bound on inf ((Ap P) over extreme P. which gives a lower bound on RQ) This involves novel combinatorial argument. We perform a "packing" of copies of X' by ( subsets AI,... A with A; = Ap, for some extreme P; and appropriately chosen and u. Then, we decompose the RHS of u = Σ =i=1 Q(X' P.) by an appropriate partition of X' involving A, 's and use the definition of e-LDP to find an upper bound on inf (P)p!P).
4 Discussions on the Proposed Mechanism
4.1 Effect of the ry approximation error
In practice, it may not be possible to find the exact value of rp such that the sum or integration of the RHS of (8) or (13 is 1. For the case of continuous space as in Theorem [33 one way implement the proposed mechanism oo in practice is as follows. First, we fix parameters on E [0, 1) and
52 that quantify error tolerance. For given P. define (x) clip (,)(z); bh(z), be h(x)) and find rp such that 9gm ( this task in Section 3.2 based on the bisection method and a numerical integration method. Then, we get a private sample by sampling from the distribution with pdf ((x) gr (x:/ J Irp (ar)dr. For the finite case as in Theorem 3.1 with the sum.
81, 1 + 52]; we delineate a numerical algorithm for
we can implement in the same way, except replacing the integral
It is important to note that ((x) E
[b(()) be be()(x)]
I+60 1-81 indicating that the resulting Q and oa
satisfy ( log 1-
-LDP as opposed e-LDP. Thus, the above implementation yields e-LDP it
used to implement Qi or Q ha with e' = log that é' 0.
1+82 and sufficiently small 8, 82 such T-8
4.2 Continuity of the proposed mechanism
In some practical scenarios, the client may not have full access to their distribution P. One example is that the client can only access to samples from P. In such case, the client may first estimate the true distribution, and then perturb the estimated distribution through the optimal mechanism. The question is how the perturbation using the estimated distribution deviates from that using the true distribution. To answer this, we show that the proposed mechanism satisties a pointwise Lipschitz property with respect to the total variation distance, and the Lipschitz constant is closely related to the factor rp we introduce in Theorems 3.1 and 3.3
8

---

Proposition 4.1. Assuming the setups of (X,P,e) P,c) in either Theorem 3.1 or 3.3 let Q" denote the
proposed mechanism Qi or Qa er.he Then, for any P. P' E P, we have
Drv (Q' Q' x
max(rp,TP) Drv (P.P))
(14)
where rp as in Theorem 3.7 or 3.3
This guarantees that for each given true P and given whenever the approximated P satisfies Drv (P, < 0rp/2, the perturbed distribution Q* (P') satisfies Drv (PP)) I 8. In theoretical perspective, this proposition implies that Q* is continuous when P and P(X) are endowed with the metric topology from the total variation distance. The proof of Proposition is in Appendix D
Q*))")
Numerical Results
In this section, numerically compare the worst-case f-divergence of our proposed mechanism with that of the previously proposed sampling mechanism. To the best our knowledge, the only work about the private sampling under LDP is [35,, hence we set the baseline as the mechanism proposed in [35]. In all the cases, we perform the comparison across three canonical f-divergences: KL divergence, total variation distance, and squared Hellinger distance, as well as across five values ef 0.1, 0.5, 1, 2, and
5.1 Comparison for finite data space
In this subsection, we compare the mechanisms the finite space, X [k] and P P(()). As
mentioned in Sections 2.3 and 3.1 the baseline mechanism has a hyper-parameter, reference
probability distribution Qo ((t)). We set the baseline generalized f f-divergence projection onto the relative mollifier. That is, for each given f-divergence, we set the baseline to satisfy Q(P) E arg minl D, (PI)), where Mr.qo is defined in Section 2.3 As expected by symmetry, for any f. choosing Qo to be the uniform distribution minimizes the worst-case f- divergence Ry (Q) among all choices of Qu for the baseline. Also, even though do not obtain the closed-form expression of (= P) for the baseline, we obtain the value of Ry (Q) when Qu is the uniform distribution. The proof of this fact, together with the precise value of R (Q) for uniform Qo. is in Appendix F.] Hence, we always set Qo to be the uniform distribution in the result about the baseline. Since we have the precise values of Ry (Q) for both proposed mechanism and the baseline, we plot such values of (Q in Figure
For simplicity, we only provide the plot for l 10. More plots for some other k's can be found in Appendix G As shown by the figure. the proposed mechanism has lower worst-case f-divergence than the bascline for all choices of f-divergences and in the experiment, with significant gap medium privacy regime e [0.5, 2].
KL
TV
Sq. Hel
f-divergence
2.0
0.8
1.5
0..
1.0
0.4
0.2
0.5
0.0
0.0
0.0
1.0
2.0
5.0
0.5
1.0
2.0
5.0
0.1
0.5
Proprosed
Baseline
Privucy burdges
Figure Theoretical worst-case f-divergences proposed and previously proposed baseline mechanisms (with uniform Qo) over finite space (k: = =0) (Left: KI. divergence, Center: Total variation distance, Right: Squared Hellinger distance)

---

5.2 Comparison for 1D Gaussian mixture
In this subsection, we conduct an experiment to compare the mechanisms when the client distributions Gaussian mixtures over real line X' = R. which is instance of continuous space case. We consider the case that each client has a Gaussian mixture distribution in I, where each Gaussian has mean bounded by and has unit variance. To avoid arbitrarily large number of Gaussian distributions to be mixed, we set an upper bound K of the number of Gaussian distributions to be mixed per client. Also, make the numerical integration tractable, distributions to lie inside an interval [-4, 4J. Unlike the finite space case, there is no known closed- form expression of the worst-case f-divergence for the mechanism in (55 The set of Gaussian mixtures not exactly of the form P = oo. hence our proposed mechanism also does not have a known closed-form expression of the worst-case f-divergence. Hence, instead, we compare the mechanisms by an empirical worst-case f-divergence.
truncate the domain of the
For an experiment, we randomly construct N Gaussian mixture distributions Pi, P2. PN P. where each Pj is generated independently according to some rules specified in Appendix F.2 After that, plot the value of the empirical maximum f-divergence maxje[N] Dy (P, (()))) for the baseline and our proposed Q. For the baseline mechanism, we use MBDE with the same hyperparameter setup [35] Section 5], except slight modification of the reference distribution to consider the truncation of the domain. The implementation details are provided in Appendix F2
In Figure we present the result for N = 100 and K = 10. We can see that the proposed mechanism has much lower worst-case f-divergence than the baseline for all choices of /ddivergences and e.
KL
TV
Sq. Hel
f-divergnane
0.4
0.100
0.3
0.3
0.075
0.2
0.2
0.050
0.1
0.025
0.0
0.0
0.000
0.1
0.5
1.0
2.0
5.0
0.1
0.5
1.0
2.0
5.0
0.1
0.5
1.0
2.0
Proposed
Baseline
Privacy budges
Figure Empirical worst-case f-divergences of proposed and baseline mechanisms over 100 experiments of ID Gaussian mixture (Left: KL divergence, Center: Total variation distance, Right: Squared Hellinger distance)
Conclusion
In this paper, we characterized the optimal privacy-utility trade-off for the private sampling under LDP and found the optimal private sampling mechanism in terms of the minimax f-divergence between original and sampling distributions, for both finite and continuous data spaces. Compared to the previous work (35] based on relative mollifier with arbitrarily chosen reference distribution, our work characterizes PUT without dependency on external information other than the original distribution, and it shown that the mechanism found is universally optimal under any f-divergence.
For future works, there may be other P and other measures of utility more appropriate to practical scenarios, which are not handled in this paper. For example, f-divergence may be an inappropriate utility loss because it only depends on -allebrra structure and does not consider additional information about geometry of X, such as underlying metric on X. Using utility measures involving the geometry, such Wasserstein distance [62 63 49], may be more appropriate for some scenarios. Also, consider the Bayesian approach instead of the worst-case approach. Furthermore, we only consider the task of releasing single sample per client in this paper. We may also consider the case of releasing multiple samples per client, rather than a single sample.
The limitations and broader impacts of this work are in Appendices and respectively.
10

---

Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for their valuable discussions and comments, particularly regard- ing the identification of alternative optimal mechanism, the advantage of the proposed mechanism over the alternative, and the effect of the approximation error on r'p.
This work was supported in part by the National Research Foundation of Korea (NRF) Grant funded by the Korea Government (MSIT) under Grant 2022R A2C2092151 and in part by Institute of Information & Communications Technology Planning & Evaluation (IITP) under 6G-Clout Research and Education Open Hub (TTP-2022--RS-2224400--2222 (MSIT).
grant funded by the Korea government
References
[1] Milad Nasr, Nicholas Carlini, Jonathan Hayase, Matthew Jagielski, A. Feder Cooper, Daphne Ippolito, Christopher A. Choquette- Caauuette-Choo, Eric Wallace, Florian Tramèr, and Katherine Lee. Scalable Extraction of Training Data from (Production) Language Models. arXiv preprint (tt::2311.170355 November 2023.
[2] Xiaodong Wu, Ran Duan, and Jianbing Ni. Unveiling security, privacy, and ethical concerns of ChatGPT. Journal Information and Intelligence, 2(2):102-115, March 2024. ISSN 29497159, doi: 10.1016//..ixxd 2023. 10.007.
[3] Biwei Yan, Kun Li, Minghui Xu, Yueyan Dong, Yue Zhang, Zhaochun Ren, and Xiuzhen Cheng. On Pro- tecting the Data Privacy of Large Language Models (LLMs): A Survey, arXiv preprint 05355 March 2024.
[4] Zhangheng Li, Junyuan Hong, Bo Li, and Zhangyang Wang. Shake to Leak: Fine-tuning Diffusion Models Can Amplify the Generative Privacy Risk. In 2024 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML), pages 18 32, April 2024. doi: 10.1 1AL10009A4TTML555570000000000000
[5] Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What Can We Learn Privately? SIAM Journal on Computing, 40(3):793-826, Jamuary 2011. ISSN 0097-5397. doi: 00.11370907550900
[6] Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy- preserving ordinal response. In Proceedings of the 2014 ACM SIGSAC conference on computer and communications security, pages 1054-1067. ACM, 2014.
[7] Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Timees, and Bernhard Seefeld. Prochlo: Strong privacy for analytics in the crowd. In Proceedings of the 26th Symposiua Operating Systems Principles, SOSP '17, page 441 4599, Association Computing Machinery, 2017, ISBN 978 450350853.
[8] Differential privacy team Apple. Learning with privacy at scale. Technical report, Apple, 2017.
Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting Telemetry Data Privately. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[10] John C. Duchi, Michael 1. Jordan, and Martin J. Wainwright. Local Privacy and Statistical Minimax Rates. In 2013 IEEE 54th Annual Symposium Foundations of Computer Science, pages 2013. doi: N0.110/FOOC..203355.
October
[11] Min Ye and Alexander Barg. Optimal Schemes for Discrete Distribution Estimation Under Locally Differential Privacy. IEEE Transactions Information Theory, 64(8):5662-56) August 2018. ISSN 0018-9448, 1557-9654. doi: 10.1 1111100011211888807777777 2882999..
[12] Abhishek Bhowmick, John Duchi, Julien Freudiger, Gaurav Kapoor, and Ryan Rogers. Protection Against Reconstruction and Its Applications in Private Federated Learning, arXiv preprint 1812:01812.0098, June 2019.
[13] Hital Asi, Vitaly Feldman, and Kunal Talwar. Optimal Algorithms for Mean Estimation under Local Differential Privacy. In Proceedings of the 39th International Conference on Machine Learning, pages PMLR, June 2022.

---

[14] Badih Ghazi, Pritish Kamath, Ravi Kumnr, Pasin Manurangsi, and Adam Sealfon. On computing pairwise statistics with local differential privacy. In A. Oh. T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 27 27129-27146. Curran Associates, Inc., 2023.
[15] Bonwoo Lee, Jeongyoun Ahn, and Cheolwoo Park. Minimax risks and optimal procedures for estimation under functional local differential privacy. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 57964-57975. Curran Associates, Inc., 2023.
[16] Hilal Asi, Vitaly Feldman, Jelani Nelson, Huy Nguyen, and Kunal Talwar. Fast optimal locally private mean estimation via random projections. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 16271-16282. Curran Associates, Inc., 2023.
[17] Berivan Isik, Wei-Ning Chen, Ayfer Ozgur, Tsachy Weissman, and Albert No. Exact optimality of communication ceamuunniation-pivacyyy-e privacy-utility tradcoff's in distributed mean estimation. In A. Oh, T. Naumann, A. Glober- son, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 37761- 1377855. Curran Associates, Inc., 2023.
[18] Racf Bassily, Adam Smith, and Abhradecp Thakurta. Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds. In 2014 IEEE 55th Annual Symposium Foundations of Computer Science, pages 464-473, October 2014. doi: 10.1 10/110090OO000000 20114.5...
[19] Stacey Truex, Ling Liu, Ka-Ho Chow, Mehmet Emre Gursoy, and Wenqi Wei. L.P--Fe: Federated learning with local differential privacy. In Proceedings of the Third ACM International Workshop on Edge Systems, Analyties and Networking, EdgeSys 20, pages 61-66, New York, NY, USA, May 2020. Association for Computing Machinery. ISBN 978-1-4503--1
doi: 10.1 N0.1145/3788679339953
[20] Badih Ghazi, Pritish Kamath, Ravi Kumar, Ethan Leeman, Pasin Manurangsi, Avinash Varadarajan, and Chiyuan Zhang. Regression with Label Differential Privacy. arXiv preprint arXiv:22 October 2023.
[21] Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta. Privacy Amplification by Iteration. In 2018 IEEE 59th Annual Symposium Foundations of Computer Science (FOCS), pages 521-532, October 2018. doi: F0.10000000.00
[22] Mengchu Li, Tom Berrett, and Yi Yu. Network change point localisation under local differential privacy. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Procexsing Systems, volume 35, pages 15013-15026. Curran Associates, Inc., 2022.
[23] Shuzhen Chen, Dongxiao Yu, Yifei Zou, Jiguo Yu, and Xiuzhen Cheng. Decentralized Wireless Federated Learning With Differential Privacy. IEEE Transactions on Industrial Informatics, 18(9)6273 6282, September 2022. ISSN 1941-0050. doi: 10.1109/T11.0000 1022.3145510
[24] Youssef Allouah, Rachid Guerraoui, Nirupam Gupta, Rafael Pinot, and John Stephan. On the Privacy- Robustness-Utilit Trilemma in Distributed Learning. In Proceedings of the 40th International Conference on Machine Learning, pages 569 626. PMLR, July 2023.
[25] Chuan Guo, Kamalika Chaudhuri, Pierre Stock, and Michael Rabbat. Privacy-Aware Compression for Federated Learning Through Numerical Mechanism Design. In Proceedings of the 40th International Conference on Machine Learning, pages 11888-18 11904. PMLR, July 2023.
[26] Yi Liu, Qirui Hu, Lei Ding, and Linglong Kong. Online Local Differential Private Quantile Inference via Self- nolfaloomaiiittion. In Proceedings of the 40th International Conference on Machine Learning, pages 21698 21714. PMLR, July 2023.
[27] Jin Sima, Changlong Wu, Olgica Milenkovic, and Wojciech Szpankowski. Online Distribution Learning with Local Privacy Constraints. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, pages 460-46644 468. PMLR, April 2024.
[28] Antonious M. Girgis, Deepesh Data, and Suhas Diggavi. Distributed User-Level Private Mean Estimation. In 2022 IEEE International Symposium on Information Theory (ISIT), pages 2201, June 2022. doi: /1109///T50566.22222999999 002.943371...9....
[29] Ruiquan Huang, Huanyu Zhang, Luca Melis, Milan Shen, Meisam Hejazinia, and Jing Yang. Federated Linear Contextual Bandits with Userl Differential Privacy. In Proceedings of the 40th International Conference on Machine Learning, pages
PMLR. July 2023.
12

---

[30] Jayadev Acharya, Yuhan Liu, and Ziteng Sun. Discrete Distribution Estimation under User-level Local Differential Privacy. In Proceedings The 26th International Conference on Artificial Intelligence and Statisticx, pages 8561-8585. PMLR, April 2023.
[31] Raef Bassily and Ziteng Sun. User-level Private Stochastic Convex Optimization with Optimal Rates. In Proceedings of the 40th International Conference on Machine Learning, pages 1838-1855 1851, PMLR, July 2023.
[32] Yulian Mao, Qingqing Ye, Haibo Hu, Qi Wang, and Kai Huang. PrivShape: Extracting Shapes in Time Series under User-Level Local Differential Privacy. arXiv preprint arXiv:2404.05873, April 2024.
[33] Kangkang Sun, Jun Wu, Ali Kashif Bashir, Jianhua Li, Hansong Xu, Qianqian Pan, and Yasser D. Al-Otaibi. Personalized Jivacc-Preseevingg Distributed Artificial Intelligence for Diniive-Twin Vchicle Road Cooperation. IEEE Internet of Things Journal, pages 1-1, 2024. ISSN 2327-4662. doi: 10.1 109/1001.202443386666
[34] Alexander Kent, Thomas B. Berrett, and Yi Yu. Rate Optimality and Phase Transition for User-Level Local Differential Privacy. arXiv preprint arXiv:2405. 1923, May 2024.
[35] Hisham Husain, Borja Balle, Zac Cranko, and Richard Nock. Local Differential Privacy for Sampling. In Proceedings of the Twenyy Third International Conference on Artificial Intelligence and Statistics, pages 3404 3413. PMLR, June 2020.
[36] James Flemings, Meisam Razaviyayn, and Murali Annavaram. Differentially Private Next- Token Prediction of Large Language Models. arXiv preprint urXiv:2403.15635, April 2024.
[37] Sofya Raskhodnikova, Satchit Sivakumar, Adam Smith, and Marika Swanberg. Differentially private sampling from distributions. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages Curran Associates, Inc., 2021.
[38] Badih Ghazi, Xiao Hu, Ravi Kumar, and Pasin Manurangsi. On differentially private sampling from gaussian and product distributions. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 77783-77809. Curran Associates, Inc., 2023.
[39] Hamid Ebadi, Thibaud Autignac, and David Sands. Sampling and partitioning for differential privacy, In 2016 14th Annuad Conference on Privacy, Security and Trust (PST), pages 664-673, February 2016. doi: 10. 119///TT 7906954.
[40] Nazmiye Ceren Abay, Yan Zhou, Murat Kantarcioglu, Bhavani Thuraisingham, and Latanya Sweeney. Privacy Preserving Synthetic Data Release Using Deep Learning. In Michele Berlingerio, Francesco Bonchi, Thomas Gärtner, Neil Hurley, and Georgiana Ifrim,, editors, Machine Learning and Knowledge Discovery in Databases, Lecture Notes in Computer Science, pages 510-526. Cham, 2019. Springer International Publishing. ISBN 978-3-030- 10925-9-5-7
doi:
1--030-00925-733
[41] Liyang Xie, Kaixiang Lin, Shu Wang, Fei Wang, and Jiayu Zhou. Differentially Private Generative Adversarial Network. arXiv preprint arXiv:
February 2018
[42] Bangzhou Xin, Wei Yang, Yangyang Geng, Sheng Chen, Shaowei Wang, and Liusheng Huang. Private FL-GAN: Differential Privacy Synthetic Data Generation Based on Federated Learning. In ICASSP 2020 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 2927-2931, May 2020. doi: 1091S0///4 202.9955529...
[43] Reihaneh Torkzadehmahani, Peter Kairouz, and Benedict Paten. DP-CGAN: Differentially Private Syn- thetie Data and I. Lahel Generation. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition Workshops, pages 0-0, 2019.
[44] Yi Liu, Jialiang Peng, James J.Q. Yu, and Yi Wu. PPGAN: -hracc-Preserving Generative Adversarial Network. In 2019 IEEE 25th International Conference on Parallel and Distributed Systems (ICPADS), pages 985-989, February 2019. doi: 10.1 11111CCCDS44477722000 10..000.
[45] Teddy Cunningham, Konstantin Klemmer, Hongkai Wen, and Hakan Ferhatosmanoglu. GcoPointGAN: Synthetic Spatial Data with Local Label Differential Privacy. arXiv preprint weXiv:2005.08888 May 2022.
[46] Hua Zhang, Kaixuan Li. Teng Huang. Xin Zhang, Wenmin Li, Zhengping Jin, Fei Gao, and Minghui Gao. Publishing locally private high- dinee-niiiiioal synthetic data efficiently. Information Sciences, 633:343-355 July 2023. ISSN 0020 0225. doi:
13

---

[47] Hisaichi Shibata, Shouhei Hanaoka, Yang Cao, Masatoshi Yoshikawa, Tomomi Takenaga, Yukihiro Nomura, Naoto Hayashi, and Osamu Abe. Local Differential Privacy Image Generation Using Flow- Based Deep Generative Models. Applied Sciences, 13(18):10132, January 2023, ISSN 2076-3417. doi:
10.3390/app1118000
[48] Hansle Gwon, Imjin Ahn, Yunha Kim, Hee Jun Kang, Hyeram Seo, Heejung Choi, Ha Na Cho, Minkyoung Kim, Ji Han, Gaeun Kee, Seohyun Park, Kye Hwa Lee, Tae Joon Jun, and Young Boung-Hak Generative adversarial networks with local differential privacy for patient medical records synthesis. Computers in Biology and Medicine, 168:107738, January 2024. ISSN 0010-4825. doi: 10.101
Hak Kim. LDP-GAN
c0mpbiomed.2023.11gm 107.77
[49] Jacob Imola, Amrita Roy Chowdhury, and Kamalika Chaudhuri. Metric Differential Privacy at the Usee-L arXiv preprint arXivv2405.02665 May 2024.
[50] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating Noise to Sensitivity in Private Data Analysis. In Shai Halevi and Tal Rabin, editors, Theory of Cryptography, Lecture Notes in Computer Science, pages 265-22622202 225, Berlin, Heidelberg, 2006. Springer. ISBN 978- 1188---54---233222 doi: 10.1007/116815 14.
[51] Igal Sason, On f-Divergences: Integral Representations Local Behavior, and Inequalities. Entropy, 20(5): 383, May 2018. ISSN 1099-4300. doi: 10.3390/e20050383.
[52] Igal Sason and Sergio Verdú. f-Divergence Inequalitics. IEEE Transactions on Information Theory, 62 (11):59733600) 6006, January 2016. ISSN 1557-9654, doi: 10. 10.10097T1220112200315111
[53] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Communications of the ACM, 63(1)); 139-144, October 2020. ISSN 0001-0782. doi: 14//4442442
[54] Elias M. Stein and Rami Shakarchi. Real Analysis: Measure Theory, Integration, and Hilbert Spaces. Princeton University Press, 2005. ISBN 978-0-691-11386-99 doi: 10.230771jctvd588188.
[55] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. Extremal Mechanisms for Local Differential Privacy. Journal of Machine Learning Research, 17(17)11-51, 2016. ISSN 1533-7928.
[56] Naoise Holohan, Douglas J. Leith, and Oliver Mason. Extreme points of the local differential privacy polytope. Linear Algebra and its Applications, 534:78-96, December 2017. ISSN 0024-3795. doi: 10.10166j.aa..211..66 20.1.00.....
[57] Ankit Pensia, Amir R. Asadi, Varun Jog, and Po-Ling Loh. Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints. arXiv preprint arXiv:2301.03:: December 2023.
[58] Seung-Hyun Nam, Vincent Y. F. Tan, and Si-Hyeon Lee. Optimal Private Discrete Distribution Estimation With 1-bit Communication. IEEE Transactions Information Forensics and Security, 19:6514 6528, 2024. ISSN 1556-6021, doi: 10. 109/TIFS.2024.344 202.3319721.
[59] Andrew Rukhin. Information-type divergence when the likelihood ratios are bounded. Applicationes Mathematicae, 4(24):415 423, 1997. ISSN 1233-7234.
[60] Stanley L Warner, Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309):63-69, 1965.
[61] F. Liese and I. Vajda. On Divergences and Informations in Statistics and Information Theory. JEEE Transactions on Information Theory, 52(10))43344441 October 2006. ISSN 1557-9654, doi: 10. 109/ TIT.2006.88177 881331.
[62] Cédric Villani. Optimal Transport: Old and New. Number 338 in Grundlehren Der Mathematischen Wissenschaften. Springer, Berlin, 2009. ISBN 978-3-540-71049-3.
[63] Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein GAN, arXiv preprint arXiv:7701.077.. December 2017.
[64] Stephen P. Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, Cambridge, UK: ; New York, 2004. ISBN 978-0-521-83378-33
[65] R. Tymell Rockafellar. Conver Analysis. Princeton University Press, 1970. ISBN 978-0-691-0185
[66] Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller. Equation of State Calculations by Fast Computing Machines. The Journal of Chemical Physics, 21 16):1087-1092 June 1953, ISSN 0021-9606 doi: (0.1963/1.1699144,
14

---

[67] Christian P. Robert. The Metropolis- Hastings algorithm. arXiv preprint arXiv:1504.01890 January 2016.
[68]
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The Composition Theorem for Differential Privacy. In Proceedings of the 32nd International Conference on Machine Learning, pages 1376-1385. PMLR, June 2015.
[69] Ryan M Rogers, Aaron Roth, Jonathan Ullman, and Salil Vadhan. Privacy Odometers and Filters: Pay- as-you-Go Composition. In Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016.
15

---

A Assumptions about the Measure Theory
The appendices assume the familiarity with the basic measure theory and real analysis. We refer the standard textbooks about the measure theory and real analysis, e.g. (54
Throughout the main paper and the appendices, we assume the followings:
For each sample space X, a o-algebra on X is implicitly given. Unless mentioned otherwise,
the discrete -allebrra is given for finite X, and
the Borel o-algebra given for X R".
A "subset" of X' always means a "measurable subset", and similarly A C. X' always means A is a measurable subset.
The "continuous" distribution precisely means the "absolutely continuous" distribution (with respect to the Lebesgue measure).
In the appendices, also introduce the following notations:
For finite X. # denotes the counting measure.
For X = R", m denotes the Lebesgue measure.
B General Definition and More Properties of f-divergences
In this appendix, we review the general definition and additional properties about the f-divergences which are important in our analysis. Let convex function f: (0, oo) + R with f(1) = 0 be given. For P, Q E P(X), not necessarily P < Q, we first take dominating measure μ on X' such that P.Q & μ (c.g., = P + Q), and let p dP dd/du, = dQ/dp. The f-divergence Dy (PIIQ) is defined as
Dj (PIIQ) = f g(z)
p(œ)) ((x))
dp(z).
(15)
We note that 15 is invariant under the choice of the dominating measure J..
Since is possible that p(z) =0 or q(x) we need define what is the value of the expression
(f(/)) for 0 or q 0 51 52
It well-known that any convex function f (0, 1) IR is
continuous, and the function
(x) -
(16)
also convex on (0, 1). Furthermore, any convex function f (0, IR with f(1) has limit lim f(x) in R U { Hence, we have the continuous extension f: [0, oo) + IR U {+x) by setting (0) lim fax), which is proper convex and continuous. By the same way, we have the continuous extension f [0, 00) + R [ Using these extensions, we define (f(()/)) = O. (f(0/g) = (0) for 9 0, and (f(p/0)
pf*(0) for p > O. Especially, if (0) oo, then D, (PIlQ) = oc whenever P < Q does not hold. (This is the case for KL divergence and x² divergence for examples) Similarly, if [(0) = Xo, then D, (PIIQ) = oc whenever Q & does not hold. Also, the maximum value of the f-divergence Ms presented in (2) can be written as M, (0) + (0).
The following additional properties of f-divergences are important in our analysis.
61
Theorem B.1. Any f-divergence is jointly convex, that is for any P1, Ps, Q1, Q2 E P(X) and 0 < 1, we have Dy (AP: + (1 x) + (1- 1))=) < AD, (PII(Q) +1 1)D1 (P2ll22)
a conditional distribution (Markov kernel) from X to y. For given Pt, P2 P(X), let Q2, Q2 P(Y) be the fush-forward measure of P1, through M, respectively. Then for any f-divergence, we have D, (P: 2 D, (Q1)lQ2).
Theorem B.2
Inequality). Let
Also, we present several equivalent expressions for the total variation distance 51 52
which are used in Appendix D In below expressions, the assumption is that P, Q < μ for some dominating
16

---

measure y with p = dP/du and dQ//4p
2 2/2 ʃ (p(x) - (((x))d((())))
1
DIv (P,Q)
(17)
| 21)())(((1))
(1(x) - -p(x))du(2)
(18)
J (xp())20(1)) (p(x) - (x)))du((x).
(19)
We introduce one more notation. For \1, X2 [0, 11, let DJ (A (1) denotes the fo f-divergence between Bernoulli distributions with Pr(1) = A1 and X2 respectively. That is,
A1
+ (1-22)f X2)1 (1
A1
DJ (Ail12)) 22
(20)
X2
We should note the following facts:
1. By joint convexity of the f-divergence and continuity of f. DJ (A1llA2) is continuous and jointly convex in (Λy, A2). (But DJ (2)) may be extended real-valued)
2. For a fixed '₁ DB (A1 (A1])2) attains a global minimum 0 at 22 = A Together with convexity,
we derive that D3 (A1 (2) is decreasing in X2 [0, A1] and increasing in X2 [],, respectively.
C Generalized Main Theorem and Proof
In this appendix, present the formal proofs of the main theorems, Theorems 3.1 and 3.3 As mentioned Section 3.3 we first state the generalized theorem with its proof, and later we show how this generalized theorem includes the main theorems special cases.
C.1 Statement of the generalized main theorem
First, let define the general setup consider. Let a (general) sample space X' be given. For positive measure p on X' such that u(x² < oo and C2 > c1 2 0, let define
(21) We generally consider the case that P P P.oz. for some C1 C2, For example, for the setup of Section 3.2 we have Per,ez,h = P Pereo. where μ is a positive measure with μ & m and dp/ = For the setup of Section 3.1 we have P((k)) = Po.1. By the same reason as in Section 3.2 may impose the following normalization condition 02,02,
Parce.m = {P P(X) : μ. S dP/du S C2 p-a.e.].
(22) Note that (x() = 1 means that μ is probability measure, that is μ P(Z). Also, note that for X' [k), distribution on [k:]
x(x') = 1, 41 <<<<< < C2. C2 > cIe..
write in normalized form P((k)) Po,k,nu where l4x h # is the uniform
First, let define the proposed mechanism, together with the related constants as the same as Theorem 3.3 For the ease of proof, we introduce an additional constant a over Theorem 3.3
Definition C.I. Let C₁, c2 f4, satisfying the normalization condition (22 be given, and let P
P Porseaae First, define the following constants determined by cı, 62
1 C1
a
(23)
02
C2
1
b
(24)
(et
1)(1 01) 02 Ci ae +
Ci
(e - 1)(1 -() ) + C2 -
(uee + -a),
(25)
b
C2 C
(e* - 1)(1 - () + 0g 4
c (ac + 1 - -a).
(26)
b
C2 C1
c
e
17

---

Also, define mechanism oo E Cx,,,. as follows:
For each PE E P, oz (P) =: Q is defined as a probability measure such that Q < p and
dQ du (x) clip
dP rP du
(x); be
(27)
where rp is a constant depending on P so that J dQ dp(x) = Furthermore, let M Mcr.ezipi
du
Pb, bb,ees,u that Re E Ma,.c for every PET P.
We should note that 1 o2a 02a
be 6(1 a)). Also, Qa clearly satisfies e- L-DDP. By the same reason in Sections 3.1 and 3.2, the values of rp may not be unique, but the mech- anism Q2, ,zu,e, does not depend on the choice of rp. Furthermore, we show that the value of
J clip df (I); b, bet) du(x) at 1ı and 12 at least and most 1, respectively.
Proposition C.2. Let C1, U, P, a, r1, be as in Definition have
11,
C.1 Then, for any P P, we
fclip
( dz (t); "e;bb,be" be" du(x) 2 212 f clip (i dy
dP
dP du
(x): be): du(x),
(28)
where, in the case of 0, we define
1 dP
= bee,
if (x) otherwise
clip
(z): b, (x):b.be))
(29)
T1 du
Furthermore, if clip dP every r E [r],
(x); be du(x)) = 1. then clip (1 dP
du df); bet) dp(x) 1 for
m du
This proposition, together with the fact that r + f clip monotone decreasing, implies that rp be chosen such that rı < rr S r2, as stated in Theorem (Again, the continuity is from (x()) < 0o and the dominated convergence theorem)
dr (æ); b, be du(x)) is continuous and du
3.3
Also, we should remark that 0 < 1 and C1 < < 1 < be c2. The first one easily follows from Ci < < C2 and the definition of a. For the second one, first we have < ae + - a < e as ae + 1 - is a propoer convex combination of 1 and e. This directly implies that b < 1 < be Next, by calculations, we can observe that
ci((e" - 11 - c1) + c2 -a) - (c2 -a)= (1 ci)(cee -22) < 0.
(30)
which implies e1 b, and
c2((e' ()(1-)))))))) - c1) - c1) c'(22 (c2 1) - c'c)) > 0,
(31)
which implics be < c2. Especially, these inequalities imply that 0 S ri < <1<, < r2.
Now, we show that under a mild 'decomposabilityy condition, the proposed mechanism Q2, is universally optimal under any f-divergences for (x' P Per.ez.ase E). After that, we show that such a mild condition holds for the setups of both of the main theorems, which finishes the proofs of the main theorems.
First, let us state the 'decomposability' condition. This condition is a formal definition of the concept of "packing of copies of X by t subsets A,, A,", which is briefly mentioned in Section (.3]
Definition C.3. Let E (0. 1) and t, u E N, t > u. We say that a probability measure μ E P(X) (a, t, deecomppssleel there exist & subsets A,, Ag,
A, C X such that p(A,) for all
i E [t], and for every z E X, we have {i E [f] x E A < u.
We say that μ P(X) is a-decomposable if for any 5 > 0, there exists t, u E N, such that a S u/t < a + 5, and μ is (a,, t, deccomposab....
We remark that (a, 1, 1) deeomposabillity means that there are disjoint subsets B1, B2, B₁ such that ((B.) = a for each i E [1]. Also, if a is rational number with a = u/l, u, E N, and μ is (a, t, u) dccomposable, then μ is a-decomposable.
18

---

Then, we state the generalized theorem.
Theorem C.A. Let c1, c2. H,C. e, P, a, b, P2 be in Definition C.1 for any f-divergences Dj, we have
If is a-decomposable, then
12 - [(22) +
--
R(X,
f(ri),
(32)
r2
1
and furthermore, the mechanism Qe as in Definition C.1 is optimal for (X, (,P,) under any f-divergences D..
As guided in Section 3.3 the proof of this theorem is broken into two parts, the achievability part and the converse part.
Proposition C.5 (Achievability part). Let c1, C2, P, a, a,b, F2 12 be as in Definition C.1 Then, for f f-divergences D,, we have
1 1- f(2))
T2 f(ri).
(33)
12 -i
T2 -
(Here, we do not need to assume that μ is a-decomposable)
Proposition C.6 (Converse part). Let c, C2 p, P, a, b, 1,,1, 12 be as in Desimition C.I and suppose that μ aedecompoabble. Then for any f-divergences Dj and for any e-LDP mechanism
P we have
1- f(r2) + 12 f(r)).
R₂(Q))
2
(34)
12 -1
The remaining of this appendix is organized as follows. We first present the proof's of Propositions
C.5 and C.6 in Appendices C.2 and C.3 in which we grant Proposition C.2 and some intermediate we show that Theorem C.4 contains main theorems, Theorems
lemmas. After that, in Appendix
3.1
and 3.3 as special cases. Finally, Appendix C.3
presents the proof of Proposition C.2 and
Appendices
C.6 and and
prove
C.7 prove intermediate lemmas.
C.2 Proof of achievability part (Proposition C.5
As mentioned in Section 3.3 the proof of the achievability part consists of two steps: first presenting an alternative mechanism and then proving that Q Co performs the f-divergence projection for any general f-divergence.
C.2.1 An alternative mechanism
Let Qf eonue E 2x,p,c be mechanism defined as follows:
Q (P) = -pP + (1 ,),,
(35)
where
c 1
7 Cec 1)(1 (1 + C2-
(36)
Since C2 > eec,, follows that 0 < 7 < 1. Also, a direct computation shows that
b = 7c1 (1 7)); be = 702 + (1 - 7) dQ eeue (P) = 7
(37)
(38)
Notice that since C1 < dr du
S 02
and
dp dy
+ (1 - 7), we have
dQ
( (P)
(x) 2 701 + (1 - 7) = b.
(39)
du
dQt
or (P)
(x) 902 (1 -2) .bc. 902
(40)
dp
19

---

Hence, (n,c)) E Ma for every P E P. implying that Qf e also satisfies e-LPP.
Now, show that
1 11 f(22) S
12 f(r1).
(41)
12 - 11
T2 -
To this end, we need to show that for each P
E P, we have
1 ri f(2)) + 72 f(r1).
Dy (P en M (P)) v
(42)
r2
Fix P E P. Let dP/dp and dQt
01 ea (P) /dj. First, we claim that
r1 5 p(x)
S r2
(43)
((x)
for j-almost every x E X. We have
p(x)
p(x)
(44)
((x)
7p(x) + +1 (1)
(1
1-y 7
(45)
7p(x)) (1
which is increasing in p(x) 2 0. Since ei 5 s(xx S c22 we have
C1
p(x)
(46)
7/1 (1 7)
((x)
702 + (1-7)
for p-almost every x E X. From 37 (38). and Definition C.1 we conclude that
p(z)
r1
r2.
(47)
(x)
which proves the claim. For the remaining of the proof, need the following lemma.
Lemma C.7 (199) Theorem 2.1). Let P. Q E P(X). Suppose that P. Q & u for some reference
measure ja on X, and there exist Fı, 72 p(w) S r2 for y-almost every x E X. Then for any dQ satisfy q(x) > 0 and Tı I
with S rı < 1 < 12 such that the densities
JP p 4. - du
((x)
f-divergence Dj, we have
S 1-n f(22) + r2 f(r1).
(PII)
(48)
f2
12
This lemma directly implies (42 and consequently (1)
C.2.2 f-divergence projection of the proposed mechanism
Next, prove that Q Qe (P) is the projection of P onto Mc for every f-divergence. Proposition 3.4. can be stated in a more general way as follows.
Proposition C.8. For any P E P and any f-divergences Dj. we have inf QEMezic2ue
Dj
Dy (PIIQ).
(49)
This proposition implies that
Dy
s Dy (p|lQt ee (P))
(50)
for every P P. and hence
Ry Ry(Q' < R2 Ry(Q S
1- ri f(r2)
+
T2 -
f(ri),
(51)
m
r2 -1
which completes the proof of the achievability part.
20

---

Fix PE E P and dP/dp. If f(0) co and p({x : p(z) 0}) > O, then D, (PIIQ) = oo for every Q E Mex.es...e thus the proposition holds trivially. Consequently, we assume either ((0) oo or p (ar p(x) = 0}) 0.
Next, we prove Proposition C.&
The optimization problem inf ozii
Dj (PIIQ) be cast the following
inf x:x (0, / g(x)}
p(z) ((x)
dp(x)
(52)
such that
((x) 2 b, Vx,
(53)
(xx) S be, Va,
(54)
I (())dp(x)=1 =1
(55)
where y = dQ/dp. Our goal is to show that q² ca (P) is an optimal solution of the above optimization problem.
Motivation for the optimality proof. To provide the motivation for the proof of the optimality of q" for the above optimization problem, we first consider the following analogous finiteddimensional optimization problem
inf )
Σ qef
Pi
(56)
q:
such that
qi
(57)
qi < be
(58)
4
(59)
for convex function f: (0, (0) 00) - IR and p; > 0. The convexity of = (see Appendix B} implies that the above is convex optimization problem. For simplicity, assume that f is differentiable. However, note that this assumption is only for simplifying the motivation for the proof, and the result holds for general f or f*
We formulate the Lagrangian for the above optimization as
n Σ
L(g. Φ, v) = Σ (p.f"(a//e (g:/p)) + di(b q:) + 4/(4 be))) +
q:
(60)
with dual variables d, vh E [0, 20)" and E R.
The Karush-Ko Maai--KuuKnnhhhhhe Tucker (KKT) condition yields:
(f"Y(g//p)) Φi + 8/s 1 = 0,
Vi,
(61)
57 58)
(59
(62)
S, 3/4 2 0,
Vi,
(63)
0.(9: - b) = cbe 9:) O,
Vi.
(64)
Now, suppose that there is a feasible point 9" E (0, )0)" satisfying 57). 588 and (59) such that
q² = clip(ps/r; b, bet) for some r We show that qº satisfies the KKT condition for some
feasible dual variables (Ø, v7 v).
For (q", Φ v) satisfy the KKT condition, the following should hold:
Ifb < p./r < bee, then we have of = ps/r. From 61 and (64) we must have Oi = v/; = 0 and (1/r).
If p:/r < b, then q.' b. Then, th: and di (f*Y(b/p)) v.
If pt/r 2 be" then q.' be". Then di 0 and د/ (fe" (be)
21

---

Now, since f" is convex, (f*y is monotonically increasing. Hence, the following should be satisfied:
If ps/r S b, then (b*p)) -F)()/))))(+)((1))))))) 2 0, and
- If pf/r be", then (1)(1//)-(())) /p:) 2. 0.
can thus be verified that (q Φ, 1, v) satisfies the KKT condition with
(fr((1/))
(( - (1
pf/r & b, otherwise,
6. 10.
4/4 (( - (PM) /p.),
if pf/r 2 ber, otherwise.
0.
Optimality proof.
Next, we present a proof for the optimality of q" for the optimization problem
inf (0,000 / {(x)s
p(x))
du(x))
(65)
((x))
such that ((x)) 2 b Vx.
(66)
<(x)) s be Var,
(67)
J (()))u(()=)
(68)
Here, note that we do not assume is differentiable. To this goal, we first review the following basic facts about a general convex function f (0, oc) - R, which may not be differentiable [64 65]:
The left derivative fx) = lim M(+th) and the right derivative (4 = h
lim f(a+h) f(a) exist and finite for every x E (0, oo), regardless of whether f is
differentiable or not.
For every 0 < x < we have (x) S fz))) S f'(v) (v)
For every v; y E (0, oo) and any g E (x', (z)), we have
f(y) 2 f(x) g x).
(69)
By continuous extension, this holds for also. That is, f(0) 2 f(z) gx for every I E (0, oo) and [f' (x)].
Let q: X + (0, oo) be any feasible function satisfying 66 (68) Recall that f'(x) := 2f(1/z) convex, and we can express ((z))(p(z)//q()) f (g(x)/p(x)) p() whenever p(x) * 0. Also.
whenever p(x) # O, we bound ('((x)/p(x))) by the linear approximation of f at g" (x)/p(z) using
169 follows:
((x) p(x))
q" (x)
9 (x(x)
('(x)
2 f*
(S*Y
(70)
p(x)
p(r)
p(x)
p(x)
Hence, we have
p(x)
((x)
{x))
p(a)s"
{())(()) + +E(x),
(71)
((x))
p(x)
where
('(x))
((x) = (
(72)
p(x))
(x'xx)
(x((x)
[(x) = p(x)
- (x)
(73)
p((x))
p(z))
22

---

Also, whenever p(a) 0, we have (())f(((()))(()) = (()) Hence, we set ((x) = p(0) and
{(x) when p(x) 0, so that
p(xx) z ((=))(()) E(x)
{()))
(74)
((x))
holds for all x E X. We note that ((x) and ((x:) does not depend on the choice of q(x:). Also, the equality holds if ((x) q" (z).
Next, as an analogous write q())dd(<))
in the above motivation for the proof, let (1/r)) Since
fale)s (()))
p(x) ((x)
du(x) - f
(q(z)) ((x)) (r (s(((c) -v) du(x)) +
(75)
/ v) + du(x)) +
(76)
Now, we define the following sets which form a partition of X:
_ < {
1
L I x
(77)
Tp
1
-pxx) S be ber).
M I T X : bs
(78)
Tp
_ be
1
x IE X:
(79)
TP
For each case of x E L,M,U, we have (x) = b, =t bet, respectively. We observe the following:
If E M, then {(z) clearly.
If x E U, then q" (x)/p(x) < 1/rp. Since (f*) is monotone increasing, we have
{(x) S v.
If x E L and p(x) + 0, then q (x))/p(xz) > 1/rp- Again, since (f*), is monotone increasing, have ((x) 2
Finally, if p()) = 0 (which implies x E I. also), then from the definition (t) = tL(tt). we have (t)
f(1/t) 1 (1/t). From (69) with y 0, we have V (f*)4 (1/rp) f(r)) rrf (rp) S f(0) ((x). Hence, ((x) 2 v for every a E L.
Therefore, since b S ((x) I be", we can write
/ (()))
p((z) g(x)) du(x) 2 / [a(x)(((=)) v) ((x)) +v
(80)
[b((xx) ,)) be be* -
tr (x)) + {()))dp(x)+ (81)
The last expression does not depend on the choice of ((r). Also, we observe that all inequalities become equality if (xx) (z). This completes the proof for the optimality of q², and hence completes the proof of the achievability part. 1
C.3 Proof of converse part (Proposition C.6)
For each A E A, let pa(x) Let Q 2x,P.e be given. Let A {A C X ((A)) = =).
C2
if treeA
if E A'AA' Since cga + c1(1 a) = 1, we have ( = 1. Hence for each
[ei
dPa A E A, we can define a probability measure PA E P
da = PA Also, note that PA(A) = C2ax
For each A A. let AA (A) Then, the push-forward measures of PA and Q(Px) by the indicator function 1 Bernoulli distributions with Pr(1) cza and AA. respectively. By the data processing inequality (Theorem B.2), we have
Dy (PAllQ(PA) 2 DJ (c2allBA).
(82)
23

---

The main lemma to proceed is the following.
Lemma C.9. Let X be a sample space. Let t, u E N, > u. Let A2, ... , C X be subsets such that for each E X, we have {i E [t] : : A S Then for any probability measures Q1,-" Qt E P(2') salisfying that Qi(A) S (A( for all i, E 14 and A C X, we have (u/t)e*
min Q.(4.) - (u/t)e + 11-(uut) SEI0
(83)
Now, by the assumption that f is a-decomposable, there exist sequences ( of positive integers such that 1j > Uj. I Uz/l;, lim Uz/lz = a, and for each j E N, there exist Ły subsets Ag, A,,,, Aj,t,
{up);= CN
such that ((AA,,) a for all i E [ty], and for every
E X, we have (i [ty] : E A H S uj. By applying Lemma C.9 to Qi = Q(Pay.). ). we (u,/t)e
obtain minke(t,] PAL, S (2
This implies that inf AEAA S (1)/5))
(ug/t)e
for all j N, and by taking the limit j oc, we have inf AEA BA
ac'
beta.
ae a1-a1-a
Since be < 02, we have be < C2a. By continuity of DJ and the fact that DJ (A1 (2)) is decreasing A2 E [0, A1], we have
sup Dy (PA))Q(PA) 2 sup DJ (c2a)]Ba)= 2 DJ (c2a)l(be*a).
(84)
AEA
ACA
follows that
R2 = sup Dy (P][(())) 2 sup Dj (Pa))Q(PA)) 2 DJ (czallbe
(85)
PEP
AEA
Furthermore, we have
DJ [c2ailbe' a) = be'af
C2a
+ (1- - ba
- C2 1 be
(86)
= be"af ( [c2x
(c - a)
+ +b(1 aaf
(87)
b(1 a)
= be beea(((2) + b(1 - (01--af(mm) (rr),
(88)
and we can derive b = 1-rı and ((1b(11111 -a) = mリー11 of Ti, 72, we have
m_1
as follows. From
30
31
and the definition
12-11
1 rj (1 - 0) 92 C
(89)
09 C1
C 02 éc
12
(90)
et
C2 C
From this, we have
1 1 T
r1
(91)
12 T1
(72 1) + (1 - m2)
(1 .I)E
(92)
() )eee + (02 1)
(1 (1- cI)e
(93)
(e
1)(1 - 9) + C2
1 1- C1
b c
(94)
C2 Ci
= befa.
(95)
Also, from above and be a + b(1 a), we have
r2 -
1 ri
be = b(1-a)) a).
(96)
12
This ends the proof of the converse part.
24

---

C.4 Deduction to main theorems
In this subsection, we show that Theorem special cases.
C.4 contains main theorems, Theorems 3.1 and 3.3 as
C.4.1
Deduction to Theorem 3.1
Recall that in this setup, A' = [k:] P - P((K) Po. where μr is the uniform distribution on [k:. That is, (C1, 02) = (0, k). The values of the constants a, r1, 72 are
a 1/k,
(97)
h
b
(98)
+ k
7i 0,
(99)
ee + k -
12
(100)
We can easily observe that 4s is (a,, k 1) -e-dccompoabble, because the sets {i}. i E [k]] are disjoint and Ma ({+) k- It follows that 14 a-decomposable. Hence,
apply Theorem C.4 By
a direct calculation of R(X, P, f)
1-n1 f(2) + -ー f(ri), we can derive the formula of
R(K,), ((k)), f) presented in Theorem 3.1 It remains to show that the mechanism Q presented
in Theorem 3.1 is the same as Qü and show the claim about the range of rp. Recall that
P(x),
Qi. = max
Ve E [k), P P((A)),
(101)
Fp e +
and we claim that rp can be chosen such that S rP S (e + k - 1)/e".
First, explained in Section 3.1 we can alternatively write
1
= clip
P(x);
(102)
rp
e +
Since P(x)
dP (z) for each E [k]] and P P([k]), dup
102 can be written
dQ (P)
dP
1
(x) = clip
(s);
(103)
dji
rr k dji
e + 1' o
+
1 dP
k
ke
clip
(x);
(104)
Tp duk
e
+
+ k
hence,
dQi,
1 dP
k
ke
(x) = clip
(z);
(105)
dju
rp dju
Et - 1'
et + ks
1 dP
clip
(x); be
(106)
rp duy
Hence, Q%
Qū po..
Second, to prove the claim about the range of rp, let us fix P E P(k))). We need to show that
1 1 Σ max (P(x), e + k
1111 -
212
max
c + k P(x).
(107)
e
The left inequality can be easily derived by
max
P(z))
> Σ
P(x) 1
(108)
c
1-
25

---

For the right inequality, we recall that b = e- Since P(z) S 1, we have c-4+)1 S Hence, again by using P(x)
(2)), we have
k das
e²
max
1-1 P(x),
(109)
-
6
1
e
clipp
P(x);
(110)
e k
-
e¹
dP
1
e²
clipp
(I);
(111)
e
1 dfi
ee +
e +
1 clip
1 dP
(z); be
(112)
k
r2
dje
and thus
e
max
- P(x), + +
(113)
1 dP
Σ
clip
(x); be
(114)
k
r2 dup
dP
clip
(z): be dpp(())
(115)
122 diu
The desired inequality follows from Proposition
C.4.2 Deduction to Theorem
Recall that in this setup, X R P P Per. Paree where 1 & m and dp/dm Note that the normalization condition (10) about (c1, C2, h.c) implies the normalization condition c). It can be directly observed that Q, Qa because for each (22) about (c1, c2 p,
PE P with corresponding pdf p(z), the chain rule of the Radon-Nikodym derivative shows that du (x) (x)
du (z:)((x)). Hence, once show that l is a-decomposable, Theorem C.4 and Proposition C.2 directly contain Theorem 3.3 as special case. Thus, it remains to show a is e-decomposable.
p(x) dP dP
dP
In fact, prove stronger statement that: is (a, t, decoopoaallee for any t, N such that t > u and a < u/t. Then, since the set of rational numbers is dense in R, this also implies that is a-decomposable.
To prove this, let us first introduce the following lemma.
Lemma C.10. Let a E (0, 1) and t,u E N, > u, a S u/t. If E P(X) is (a/u,t, decomposable, then y is also (a, t, u) deecomppssbee..
Proof. In this proof, assume that the sum and subtraction operations performed in subscripts are modulo operations, with the identification that 0 t.
By (a/u, u, t, J-decomposabilitty there are t disjoint subsets B1, B2, B. such that ((B,) = a/u for each E [4]. Using this, for each [t]. define A, as A; U9-0 Bu+j. As B,' are disjoint, have u(A.) Ej-d p(Br+s) u (a/u) a for all contained in exactly sets among A.. A.. which are A,, A.-1.... ,A-utt Furthermore, if & & B; for all i E [1], then x is contained in none of A, Hence (i E [4] : E A:} & for all X. Thus y is (a, decoomosp.......
[t]. Also, for each E B, is
By this lemma, suffices to show that for any E such that t 2 2 and a S 1/t, is (a, t, 1)- decomposable. As μ < m, the map s R + ( s] x@xxR\=>) continuous, and as - and oo, we have n(((00,, s] -> and 1, respectively. Hence by the intermediate value theorem, for each i (4), there exists s; R such that u((-oc, s) x|xX0 1= = ai. Then, setting A = (-oc, 81 R=-1 and A; = (si-1, x:] x R= for i > gives the desired A,'s i in the definition of decomposability.
In conclusion, is a-decomposable, and hence Theorem 3.3 can be deduced from Theorem C.4
26

---

C.5 Proof of Proposition C.2
Let P E P be given. Let dP and again assume that o₁ S <p(x S C2 for all x E X. Similar du to the proof of the achievability part, for each > O, let us define the following sets which form partition of Xe:
L = x E :: x: pp(x) < <b].
(116)
M, = 1 E X: : .s v pl(x) S be
(117)
U, = x EE::
p ,p(x) > be
(118)
For 0, we let Lo = fo X p(x) = =], U0 fo X p(x) 0}, Mo 0. Also, let 4. (x) = clip (,)( bet). Then, (-(xx) = b, pz)) be for x E Lr, Mr, U, respectively.
First, we show that gr, (x)dd(()) 2 1. We divide the case of ei = 0 and ei > 0.
Suppose first that c1 = 0. Then 11 = 0, +/2 and b = -- Observe that
/ p(z)dp(=)) / p(x)du(x)) s cop(Uo); 1uo
(119)
hence ((()) 2 1/c2. It follows that
f 4r (x))d((x)) = bbo( + be u(U6)
(120)
-b(1 - m(Uo)) - be p(Uo)
(121)
-b(e- 1)₂(U0) +
(122)
biee - 1)
+b
(123)
C2
e + + -
x
=
(124)
22
Next, suppose that 0₁ 0. Then ri O. From p(z) C1. we have p(1)) 2 b. Hence
Lm = Thus
/ J (x)d
= 1 I p(z)du(x)) + be ((Ur)
(125)
Mr.
1 (J p(x)du(<) CE ())((U))))
(126)
m M
Let S1 = SM., p(z)du(z) and Ti = u(Ur,). so that
1 [ qm. (x)dp(x))
-(s - (S1 Ti).
(127)
TI
As Sp(x) S c22 have
S S p(x)dp(z) clu(Mr,) ci (1-))(U)) c1 (1-T))),
(128)
Mr
and
/
p(x))p(x)= 1 p(z)dp(()) s c2u(Ur)) = c2.
1 1- S 51
(129)
Nr.
From these, we can get
S + TT 2 c1,
(130)
S + T > 1.
(131)
27

---

As c1 < <cIe" < C2, we can express Cié' as a convex combination of e and
C2 CIE²
Ge¹
C1
Cieº
Ci
+
C2.
(132)
02 C1
C2
- C1
Hence, by taking 02-c,e" 02-01
equuttin (300
qee
lequation 131
we get
02
2 Cieº
cie² ci
S
2
C1 +
(133)
C2 C1
02
2 Gie
+ e" -
(134)
02 C1
(e* 1) - (1) + 02 C1 C1
(135)
C2 - C1
r1-
(136)
Thus we have J gr, (x)du(x) 2 1.
Similarly, we show that f gr. (r))d(()) s 1. from p(x) S we have p²) s 2 = be Hence
Ura = 0. Thus
/ (=) = br( + - / p(x)du(x))
(137)
Mrz
1
C2E O2e "u(Lrr)) + / p(w)du(t))
(138)
M...
r2
Similar as above, let S2 ((lrr)) and T2 = -SM., p(x))dp((()) that
/ (x)
1 - (cze 'S2 T2),
(139)
T2
and, we have
T2 = / p(z)du(ax) S c2p(Mrg) = c2(1 - (((rr))) = =02(1 S2)
(140)
Mrz
and
1 1 T2 = 1 - / p(z)dn(I)=
/ p(x)du(Z)) 2 cIH(Lm)) S2. Jmm
(141)
Mr2
hence
C2S + +T2 S C22
(142)
S1 + T2 S 1.
(143)
As ei S oze
S C2 we have
c
C2e
C
C1 +
C2
(144)
C2 Ci
02 -
and by the same reason, we have
02 O2e
O2e T - C1
C2e -S + T2
(145)
C2 C1
C2 12- C1
1 c + O2e
C1
(146)
02 C1
E 1)(1 - 01) + 02 C1
C25
(147)
C1
(148)
Thus have f gro (x)d((x) < 1.
28

---

Finally, we show that qr. (z)dp(>>) = 1 implies (x))(((( = 1 for all r E T2]- Let us assume J gr, (x)du(x) 1. We first claim that: p(æ) = for p-a.e. a E Ur, and p(r) = c1 for pea.c. x E XU Again, we divide the case of c₁ = 0 and cj > 0.
Suppose first that 01 = 0. By tracking the proof of f 4r, (x)dd((a) 2 1, We can observe that the equality f yr, (x)) = holds if and only if μ(Uo) = 1/02, and only p(x) = 62 for p.a.e. E Up- By definition of Uo. we have p(x)) = 0 = for all E X Hence we get the claim.
Next, suppose that 61 > 0. Again, by tracking the proof of f qr, (z)dp(z) 2 1, We can observe that the equality qr, (x))d((z=)
is equivalent any of the following statements:
Both S + ciTi = 01 and S1 + ozli = holds.
Both JM., ((z)d((z)) = c,H(M,)) and Su., p(z)dp(x) = csu(Ur,) holds.
p(z) = ci for u-ace. I E M,, and p(æ) = og for p.ace. x E Ur.
Since L, 0. also get the claim.
WLOG, assume that p(x) = e2 for all x E Un,, and p(x) = ci for all E X.U Then, for every E (2), we have the following:
For each x E Ur,, we have pp(x)) 2 = be", hence gr(x)) = be..
For each X'
If c1 = 0, then p(r) = 0. (x)) = b. and
If c 0, then 11 > 0, tp(x)) < b, hence again gx(xx) = b.
Also, we have = [(())d(()) = (o)(Ur,) + ci (1 ((U,))) hence ((Ur,) = 1-01 = a. It follows that for every E (21, we have f q, (x)du(x) u(U,) + b(1 ((Urr)) be + b(1 - a) This concludes the proof.
C.6 Proof of Lemma
Although the proof can be found in 59 we present the proof here for the completeness.
If ri 0 and f(0) oo, then the RHS of the inequality want to show is oc, thus it becomes trivial. Hence, we may assume that either ri > or f(()) < cc.
By the assumption, p(z)//(x)) is the convex combination of and r2 for p-a.e. x E X, as follows.
p(x)/4(x) (p(x)/g(x)) -ri T2-1 rı
- (p(x)/g(x))
(149)
V2 71
Hence, by the convexity of f and a p((x)dd(z)= = {a()dp((a) = 1, we have
(PIIQ) = / ((=))(((=)/(())dddu
(150)
< / ((x)) (p(x)/q(z)) - f(r2) + 12 - (2=((())/(())) s(ri)) du(())
(151)
--
12
/ p(x) r19(z) f(22) + r2q(2) (a(())>ple -((x) ((1))) du((x)
(152)
122 11
r2 1i
1-T1 TI f(22) 1
12 ri -2- f(rz).
(153)
C.7 Proof of Lemma
C.9
First, we claim that for each E [t - u]. we can construct a partition (BE1, Bi,,... B of Auti into u (measurable) sets, such that for each E [u]. the sets Aj, B1,j. B2.j... Br-a.j are disjoint. The construction is in the inductive way as follows: Given e [t-u]. suppose that we have constructed
29

---

such partitions of Aut1,' Auti-1 such that for each j E [u], B,,, ,,, are disjoint. Let Ci, A, U (U Bro). Then for each Autis at least one of C,2, Ci.u does not contain æ, because
Σ (x)
Σ
(1
Ic,, = --
1 ca (x)
(154)
j=1
j=1
(x)(t) +
Σ
1 mm
mm) (x)
= )0000=
Σ
11,(11 (1)
Σ
1 1-1
1 Ben (2)
(155)
k=
j=1
j=l k=1
i-1 a Σ
i-1 Σ
(x)
B (x)==- = Σ 1a, (2)
1 (z)
(156)
j=1
zu (u 1) 11
(157)
where the last line is from that since x E Auti, at most u 1 sets among A1, A2, Auti-1 can contain x. Hence, setting
Br = for E Auti :j min (j [u] of
(158)
gives the partition {BI,, B,,,.... B,,,) of Auti, such that for each j E [u]. Cit and Bi. are disjoint. This implies that Aj, B1.5 B2,,'",, B., disjoint.
Now, let l min (A,). Using these partitions, we can now show that
U Brs) )) Ai=1
Σ xx)x) 2 Σe,
2,
A
(159)
1=1
" t-
t-u
Σ (4,44)) + ΣΣ
(j(Bk.) = (((A,)
+
ΣΣ (
(160)
1=
==1
k=1
Σ 2444
Σ (Au+t)
(161)
2 Σ (((4A) +
Σ
e
(uutt((Att)
(162)
5=1
k=1
2 2 (00-10 ((-)))).
(163)
Hence
u
(u/t)e-
8 <<
(164)
u u (t (t- u)
(u/t)e² +1 +1 (u/t))
D Proofs of Remaining Propositions
We present the proofs of remaining propositions in the paper. Propositions 3.2 and 4.1
D.I Proof of Proposition 3.2
By the assumption, there are subsets { of X' which are pairwise disjoint and P.(A.) for all E N. Let us pick Po E P. and let Qu = Q(P)). Since A,'s are disjoint, we have < 0p. Hence, we have lim Qo(A.) 0. Also, by definition of cI.DP, for any PE P and E N, we have (A,) S e*Qo(As). Especially, this implies (A). s (A.)) and thus lim, ((P))(A)) = 0.
D (o.A.) Qo (U Aa)
30

---

Now, similar to the converse proof in Section let 8 = (A.) Then, the push-forward measures of P; and Q(::) by the indicator function 1, A are Bernoulli distributions with Pr(1) = 1 and B4 respectively. By the data processing inequality (Theorem B.2) we have
C.3
D, (P:IQ((P))) 2 Dÿ (1118).
(165)
Since lim; B 0, by continuity of Dj, we have
QQ) lim Dy ((P:))((())) 2 lim DJ (1113)) DJ (1]]0) My,
(166)
where the last equality is because two Bernoulli distributions with Pr(1) 1 and Pr(1) 0. respectively, are mutually singular. Hence, we must have R2(Q) = My.
D.2 Proof of Proposition 4.1
For generality, we prove that the statement of Proposition 4.1 holds in the general setup in Definition That is, for the setup in Definition C.1 the mechansim Q* Qo satisfies
Drv (P)) < TP) Drv (P.P')
(167)
for all P, E P. As the mechanisms Q and Q h, in the paper are special cases of Qù es,pee a proof in this general setup induces Proposition 4.1
Now, let us assume the setup in Definition C.1 Let P. P be given. WLOG, assume that rp rpr. Let dP/du, p' dP' /du, and (xx) clip (()); be ) g'(x) clip (p p' (xx); b be so that q (P) and of = (P'))/" For simplicity, we denote clip(x) == clip(1;; b, be
We first note the fact that clip(x) is monotone increasing and I-Lipschitz in æ. From this and the equivalent expressions of the total variation distance in Appendix B we have
Drv (Q)(),,(((P))
(168)
(g(x) - o (x)))d((x))
(169)
p' ((r)) )) du(x)
S
clip
Fr ppxx) - -clip
(170)
rp"
1
clip
p(z)
clip
rp p'(x)) dp(x))
rP
+ / 1=9())200()))
{1 rp. ( du((z)
clip
_ pp(xx)
-clip
(171)
TP
(p(x)= -p'(x)) du(x)) +0
(172)
\100()224(10)) (1)
rp
1
/ (p(x) - (x)))((p(z)
<
Drv (P, P').
(173)
TP
TP
This ends the proof.
E Behaviors of Proposed Mechanisms
In this appendix, we present the formal proofs for the behaviors of the proposed mechanisms presented in Sections 3.1 and 3.2
We first observe that the formula of the optimal worst-case -diivereence general case
- r1 f(r2) + r2 - 1
r1 f(ri)
(174)
T2 ri
T2
31

---

is the y-coordinate value at z = 1 of the line segment joining f(r)) and (r2, f(r2)). As is convex, this formula increasing in 122 and decreasing in ri, provided that r1 1 12.
Now, let us present the proofs.
If f(0) = ao and P contains two mutually singular distributions, then R(X, P, e, = 00.
Proof. Let Pt, P2 E P be mutually singular distributions with disjoint supports A,, A2 C X respectively (That is, Pi(A)) P2(A2) 1 and A n A2 0). Suppose that Q is
an e-LDP sampling mechanism for (X, P) such that R, (2 < co. Since f(0) 0C. D, (P)lQ) < oC, implies Q < P. Hence, as D (P:(Q((P)) < oo and P((A.) = 0,
we have Q(4 P.)
for each 0, Q(4f) = O. Now, since A1 0 A2 = 0, we have A7 UA = X. But by the union bound, Q P2) I (49 P2) Q(5 Pa) which contradiction.
2. As satisfies e-LDP, we have Pa) <
Q(49)
Hence, R (Q) do for every cDLP sampling mechanism Q.
From now, assume f(0)= < co.
Let us first prove the behaviors for the case of finite X' in Section 3.1
R[[A), e, is decreasing in and increasing in k.
Proof. Recall from Appendix C.4.1 that the case of X [k). P P((k)) can be fit into the general case with
= 0,
(175)
e + k 12
(176)
et
Here, 12 is decreasing in and increasing in k. As 174) is increasing in r2, get the desired claim.
For a fixed k we have ((K), P(([)) f) - 0 as
Proof. As c + co, we have 72 As continuous, f(1 0, and f(0) < oc, we obtain from (174) that
1 0 f(1) f 1
1 -
R(K), (([)), c, - 1-0
f(0)
(177)
as é - DO.
For a fixed l. as + 0, we have
+ 1/k for every P E P((k)) and x E [k].
Proof. We know that - S Qi. < - As + 0, both of c and
converges to f hence we get the desired claim.
Next, let us prove the behaviors for the continuous case in Section 3.2
If e = 0 and f(0)) = xo, then R(R"", Pa Pay.eahhe e; f) = oc.
Proof. Since r2 1 and Fi 0, we have ra-1 r=-1 ra-1 f(0) oo, which proves R(R"" P Po, 0o.
> 0. Hence 1-- f(r1)
T--T1 72
12
For a fixed c2). R(K", Por.eg,h f, is decreasing E.
Proof. We can observe that r1 is increasing in and 72 is decreasing in e. Since 174 is increasing in r2 and decreasing rı, we get the desired claim.
For fixed (c1, (2) with e₁ 0,
oo, have RRR", P Per.o G, 0.
Proof. We can observe that rı = 0 and r2 - 1. Hence, by the same argument as 177 we have the desired claim.
32

---

F Detailed Explanation of Setups in Numerical Results
We present details about the setups in producing numerical results in Section 5 and generating Figure in Section [
In this appendix, for each μ E R2, NM = (2x) det(E) exp |a - " ((w-H)
is the pdf
of the n--iienniionl Gaussian distribution with mean f and covariance E. Note that we denote (u, Σ) to refer the Gaussian distribution itself with mean j and covariance matrix E.
E1 Explanation for numerical result for finite data space
In this appendix, we show that among the choices of Qo in the baseline for X' = [k]. choosing Qo be the uniform distribution minimizes Ry (Q), and present the precise value of R2(QQ, for the baseline with uniform Qo. From now, let us fix l; e, f, and we denote QQ to mean the baseline with the reference distribution Qo- Also, let 6₂ E P({))) be the point mass at [k]. Recall that
.M... (Q P(X): e -=2 Qo(A) S QQ(A) Qu((A), VACA),
(178)
and we set the baseline to satisfy that
D, (PllQq. (P)) = inf (PII))
(179)
QEM..90
First, if Qo(x) 0 for some [k), then Qq. (x|P)) < 20(2)) = 0, Qq. (x = 0 for every P E P(k)). Especially, Qo (r) O, and this implies that Qqo (6,) and on are mutually singular. Hence,
R (QQ.) 2 Dy (6 (8)) My,
(180)
concluding that (QQ)).) = My. Hence, to minimize Ry Qq.)), it suffices to set Qu(x) > 0 for all [R:). Hence from now, only consider such Qu-
We note that for every x E [k] and P E P((k)), we have we have Qq,(2 I e²(2Qo(z) and furthermore
(zo =1
Σ (v)
(181)
ME(
Σ e-1220()))
(182)
v =1 Q0(x))
(183)
= + (1 - 1112)
(184)
Letting
B(t) = min ( -/2 1 + (1 E {12))
(1855
we have
Qgo (x|P) < B(Qo(=)).
(186)
Note that (t) is increasing in t. Now, for any I E [ki], we have
R₂ (Qx0))) 2 Dj (5.. QQ0 (6x))
(187)
QQo (x(0=))
Σ (r(
(188)
QQ0 (2)(5x))
[E(
1
Qq. (x(0w))
+ (1 Qq (z))
(189)
(20(0))
We can observe that the last term can written in the form of the optimal worst-case f-divergence I74 with ri 0 and r2 1/Qq, (z)(6)). In other words, let
R(),,r2)
1
f(22)
12
f(11).
(190)
F2 - r1
r2 -
33

---

Then we have (Q(QQ.) 2 R(0, QQQ (2)62)). (z)2))
As noted in Appendix R(11 r2) is increasing in r2 for 5 < < 12. Since QQ (z)(x) S B(Qn(z)), we have
Ry(Qq.) 2 9(011/B(Qu(z))
(191)
Since this should hold for all x E [k], we have
Qy(Q
max R(0 1/B(((()))
(192)
xE[
Since minze[M Qo(x) S 1/k for all Qo ((.)) and B(t) is increasing I, we have
Qq(QQ.) 2 R(0, 1/ [())))
(193)
Now, let μı be the uniform distribution over [k]. We will show that
R2 1/O01/
(194)
which suffices to prove that Qo ja minimizes (Q,))..
We observe that Ma,u is a convex set in P([k]). Since Dy (PIIQ) is jointly convex in (P. Q).
we obtain that Dy (Pl Que (P)) minqeM.... D, (PIIQ) is convex in P by [64 Section 3.2.5].
Hence, the maximum of D, Qu (P)) occurs when P is one of the extreme points of ((kk).
that is, the point masses 6g. By the same arguments as in 187 R(0, 1/Q(x)), and hence
189
we have Dj (6xllQ)
(Qm))
sup Dj (PIIQuu (P))
(195)
PEP((K)
max Dj (6.z Que (82)) zE[R]
(196)
maa inf =E(k] QEMc.ie
Dy (6xz (Qx
(197)
= max inf =E|k| QEM
R(0,1/((z1)
(198)
1
R 0,
(199)
min suPqeM...a Q(x))
Also, by the same arguments as in (81 184) we have
(x)) < B(1/k), AQ Me,u [k]
(200)
Now, we will show that supQe. ((x)= B(1/k) for any x E [M:]. To show this, will prove that there is a distribution Q E P(()) such that Q(x) B(1/k) and Q(y) 1-801k) for all y E [x], and this Q is contained in Me,ee suffices to show the followings:
A-1
1 k
1/2 < B(1kk) < min
1, ee/2
1
(201)
k
1 k
e/2
1/2
1- B(1kk)
1-1 < min
1, eet/2
1
(202)
k
We note that whenever 0 St 1, we have
B()) min (e 2, - - + (1 e1=3))) 2 f, and
B(() < c/2 + (1---(12 = (1 t)e -/2 < 1.
From these, we can easily observe that B(1/k) S min {1, / }. and
1
12 <
< B(1/k).
(203)
k
k
34

---

Also,
1 - B(1/k)
1 - (1/k)
min 1, e2/2
(204)
h-1
k --1 k
k
B11/k)
1- (1/((( + (1 e =-2)
1
c/22
(205)
k
k
This shows that suPqeMc..s.
Q(z) = B(1/k) for any x E [A.] Thus,
min =E(k] QEM Q(x) B(1kk),
sup
(206)
Ry(Quu)) = (2, B(1/k)
(207)
This ends the proof that Qo μgg. minimizes R2 (Qq)). and (Qn)) (0011/B()))))
F.2 Explanation for the experiment in ID Gaussian mixture
The precise description of the set of possible client distributions in our experimental setup as follows:
Σ NoN [a] I-1
p P: p(p))
Σ x
1, 144 S
[ E X:N NN
(208)
Each of Pj P is generated by choosing As. and μ4 in 2008 follows: (i) First, choose the number of Gaussian distributions by first sample from Poisson distribution with mean ko (which is chosen beforehand), and let min(k + 1, K), and (ii) after that, sample each of
M1.-. H4g. independently from the uniform distribution on [-1, 1], and sample (A,, As) from the uniform distribution on P([A]).
The implementation of our proposed mechanism is as follows. We can observe that
[ No.1 [c]ddr [ -33) (b-5),
NNNma,
inf Ne(- 1111
= +(3)
(209)
where & is the edf of the ID standard Gaussian distribution, and for each w E [-4, 4J. we have
Σ A. S sup N Nwn1 = /2x
exp -
(210)
#El-1,1]
Hence, we have P c P o. Po,eg.ho where
h(x) exp --mmx(([])1100) - 1,0)]3/2)
( - (--5) (1),4(((z)
(211)
and 02 = f M(x) h(x)/e2- When implementing our proposed mechanism, we use the bisection method to find constant rp. We predetermine the error tolerances ,1, 52 2 0, 8, < 1, and
we terminate the bisection method to find r' if the integration (13) lies in the interval [1- 1 82]. As mentioned in Section 4.1 to consider the enror tolerances, we actually implement Qi (P),
with e' = e - log 1+6. 1-4
In the experiment in the paper, we use kn and 6, = 62 = 10-5
For the baseline, tures"], except a slight modification in a reference distribution Qo- (35), they set the standard Gaussian the reference distribution, Qo A0, 1). To consider the truncated domain |-4, 4], we set Qu as the truncation of the standard Gaussian, that is, Qo has a pdf
the same hyperparameter setups in 135 Section 5, Paragraph "Architec-
No.1
(x(x)) = [ No.1 [x]dæ
1 ((-4.4
(212)
35

---

The baseline has many other hyperparameters not specified in [35 such as the proposal distri- bution used for the Metropolis-Hasting algorithm 666 67]. initial model parameters for the weak learner, etc. We noticed that the code for (35 is available at utlhttps:/ /ot::://ithiie /ggtttu........ com coomkarrkaaamm http:oosteedeenssiiieeeeeeeeeeee
and hence we made every effort to faithfully repro- duce the baseline with exactly the same hyperparameters, including those not mentioned in the paper [35]. However, subtle variations may arise due to differences in the programming languages employed; we used Python, while [35] used Julia.
F.3 Explanation for Figure 1
For and Ø > the Gaussian ring distribution with & modes and component-wise variance x² is the mixture of k Gaussian distributions in IR² with equal weights, where each Gaussian distribution has the covariance x² 12 and equally spaced mean in the unit circle, and one of the
Gaussian distribution has mean (1, That is, it has a density N [z], with μi =
(cos 2ml sin 201 In Figure I the left image is the pdf of the Gaussian ring distribution with k = 3 and o² 0.5. It is used as a client's 's original distribution.
For our proposed mechanism, similar to Section 3.2 we use the setup that consists of Gaussian mixtures, where each Gaussian has mean within unit ball centered at the origin and has covariance 0.5l2. that is, P EEi= >,N I2)
A 2 Σ X = 1, ||= S 1}, with x² 0.5.
We can also observe that P Po... for h(x) 2na2 exp
max max (0,|==]|==]] 11))
2
Same as Appendix F.2 we have Po,1. -.ii=Pooc... Po.c2, where C2 = f h(x)dr, h(x) = h(x)/c2. Hence, we use Q k.e The implementation of Q c2,, (P) is the same as the description in Appendix F2 with 8 = 10-5, For the baseline, we also use MBDE with the same hyperparameter setup as [35] Section 5, Paragraph "Architectures]] with the (untruncated) 2D standard Gaussian as a reference distribution, Qo = (0,0
36

---

G Additional Numerical Results for Finite Space
In this appendix, present more numerical results for the finite space case explained in Section 5. for other k. We present the result for k = 5. 20, and 100 in Figures 7 As shown by the figures, the proposed mechanism always has the smaller worst-case f-divergence compared the baseline, as the optimality is proved for the proposed mechanism. However, the performance gap between two mechanisms decreases as becomes smaller and becomes larger.
Kl
TV
Sq. Hel
1,5
Warst f-divergesees
0.6
1.0
0.11
0.5
0.2
0.0
0.0
1.0
Proposed
Baseline
Privucy budges
Figure 5: Theoretical worst-case f-divergences of proposed and previously proposed baseline mechanisms (with uniform Qo) over finite space (k: 5)
KL
TV
Hel
0.8
Worst (-divergance
0.6
0.6
0.4
1
0.2
0.2
01
0.0
0.0
Proposed
Baseline
Privacy budget
Figure Theoretical worst-case f-divergences of proposed and previously proposed baseline mechanisms (with uniform Qo) over finite space (k 20)
KL
TV
Hel
Worst f-divergenee
0.8
0.75
0.6
0.50
0.4
0.25
0.2
0
0.00
0.0
0.5
Proprsed
Baseline
Privacy budgget
Figure Theoretical worst-case f f-divergences of proposed and previously proposed baseline mechanisms (with uniform Qo) over finite space (k 100)
37

---

H Instructions for Reproducing Results
In this appendix, we provide instructions for reproducing the experiments and figures in the paper. For a detailed document about the code, refer to the provided file READKE. md. For the tasks consuming large time, we also specify the running times of such tasks. We do not specify the running times of the short tasks consuming less than 5 seconds. All experiments are performed on our simulation PC with the following specifications:
OS: Ubuntu 22.04.1
CPU: Intel(R) Core(TM) 19-9900X
Memory: 64GB
There are a few remarks:
Although we expect that the codes can run and reproduce our results on sufficiently recent
versions of Python libraries, we provide the information about the anaconda environment used in the experiment in environment.yyan yaml for the completeness.
The provided codes contain some lines make the figures TEX fonts. Running such lines requires the ВТEX to be installed in the experimental environment. We can remove the following lines disable using TBX:
matplotlib. use use ("pgf")
"pgf. texsystem" "pdflatex", 'font. 'serif',
text. usetex': True,
'pgf rcfonts' False, CCompteer Modern Roman',
H.1 Instruction for producing Figure
Figure be obtained by running the code plot_ Gaossinnusning.... py, without any program arguments. We measure the running time for initializing the mechanism and and calculating the sampling distribution for the baseline (MBDE (35) and our proposed mechanism. The measured running times in our environment
follows: (unit: second)
Initializing the mechanism
Baseline: 0.80
Proposed: 1.22
Calculating the sampling distribution
Baseline: 35.19
Proposed: 664.18
H.2
Instruction for producing Figure
Figure 2 can be obtained by running the code visualizee py, without any program arguments.
H.3 Instruction for producing results for finite space
The results about the theoretical worst-case f-divergence for finite space, Figures 3 can be obtained by running the code plot_fine finite. .yy with a program argument --k to specify the value of For example, in the command line, the aforementioned four figures can be generated by the following commands, respectively:
python plot_finite.py --k 10
python plot_ plot_finite.py --k 5
38

---

python plot_finite.p py --k 20 python plot_finite.p --k 100
H.4 Instruction for producing results for ID Gaussian mixture
The experiment of ID Gaussian mixture in Section 5.2 consists of the following two codes:
1. exp_1DGaussMix. py
This code performs an experiment on single e. We can provide two program arguments eps and seed to specify the values of and the random seed, respectively.
2. alot_1DGaussMix py
This code generate the plot like Figure 4 from the results of exp_1DGaussMix.p
The results the paper, Figure can be obtained as follows:
1. First, the following commands:
python exp_1DGaussMix, py --eps 0. --seed
python exp_1DGaussMix, py --eps 0. 5 --seed
python exp_1DGassMMix. py --eps 1.0 --seed 3
python exp_1DGaussMix,p py --eps 2.0 --seed
python exp_1DGaussMix, py --eps 5.0 --seed
These can be run in any order or in parallel. Check that all of the five result files 1D0aussMix_epps
npy corresponding to five values of are generated. In our environment, running all of the five commands parallel consumes 3h 13m 35s. 2. Then, the code plot_ 1DGausaMix. py without any program arguments.
I Limitations
Our main contribution lies in proposing minimax-optimme mechanism, and we present several experimental results based on synthetic data support the superiority of our mechanism. However, since we have not conducted experiments based on real datasets, the analysis of performance in real-world scenarios insufficient. Also, our PUT formulation in the minimax sense provides optimal utility in the worst case, which may result in reduced average utility when prior information is given. Finally, our implementation of the proposed mechanism requires large amount of running time due to numerical integration, which makes experiments in multidimensional spaces challenging.
J Broader Impacts
Our proposed mechanism can be utilized for privacy protection the field of generative models, which has recently received significant attention. A major deterrent the adoption of privacy protection algorithms in weal-world scenarios is the potential performance degradation. Our PUT- optimal mechanism, that minimizes the loss of utility given the privacy budget, alleviate such concerns.
We should note that LDP mechanism provides certain level of privacy protection but cannot guarantee complete privacy protection without completely sacrificing utility. Additionally, clients typically provide multiple data points through various channels, and when these data are combined, it can lead to greater privacy leakage [68 (6).
39

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We clearly stated the main contributions and scope of our paper in the abstract and introduction (Section]
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We stated the limitations of our work in Appendix
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
40

---

All theorems, propositions, and lemmas in the paper include all the necessary assumptions, and are accompanied with either the proofs in the appendices or relevant references.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provided instructions to reproduce all the figures and experimental results in Appendix H
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
41

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We plan to make the code attached the supplementary material publicly open after the review period. Also, the instructions to reproduce the results are fully specified in Appendix
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
weellii/ggiies//CCe Sawelee//oooSSbbmiiiaaae SorooddSumisssioPPP... wwriiisssiiipcyioioo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We presented enough details to implement proposed mechanism, and attached the code for implementing both the proposed mechanism and the bascline in the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: As the main contribution is theoretically characterizing the worst-case utility. we focused on extracting the worst-case utility in the experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
42

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provided the information about the computer resources and running times for the experiments in Appendix H
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
Our research conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discussed both the positive and negative societal impacts in Appendix J
Guidelines:
The answer NA means that there is no societal impact of the work performed.
43

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do recognize any risk for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best. faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: All of the codes only use the basic Python libraries like numpy, scipy, torch, and so on. No other external assets are used.
Guidelines:
existing assets. The answer NA means that the paper does
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
44

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
batasets.papersstt
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: As mentioned in Appendix H we documented the details of our codes in the file README. md, which provided by the NeurIPS Code and Data Submission Guidelines.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
45

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
46


Reviews:
[{"review_id": "1mRQqCTLM5", "reviewer": "Reviewer_D3Yh", "summary": "This paper considers the issue of protecting probability distributions with local differential privacy when they are sampled. This problem has been recently studied in view of potential applications to generative models. In particular, the paper studies mechanisms that, given a distribution, produce a \"sampler\", i.e., a sampling mechanism that can be seen as an obfuscated version of the original distribution and which is used to produce samples in replacement of the original distribution.  The paper investigates the privacy-utility trade-off of the proposed method, where utility is measured in terms of f-divergence between the original distribution and the sampling distribution.", "questions": "Can you please explain why knowing a distribution presents a privacy risk?  In general, the problem in privacy consists in protecting the individual data point, while allowing statistics to be derived, including the inference of the distribution from which the data points are drawn.", "limitations": "The limitations are discussed. In particular, the paper points out that there are other notions of utility (distances between distributions) that could be considered.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "+ The proposed method is shown to be *universally optimal*, i.e., the produced sampling mechanism minimizes any f-divergence  wrt the original distribution\n\n+ For finite data spaces, the paper presents a closed-form expression for the utility of both the proposed mechanism and the baseline method proposed in [35], allowing for an exact comparison of the utilities.", "weaknesses": "- The paper should justify better, in the introduction, why inferring a distribution presents a privacy risk. In general, in the DP literature, we want to protect an individual data point, not the distribution that can be inferred from the data collection.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Response to the question on the motivation of protecting distribution\nWe thank Reviewer D3Yh for thoroughly reviewing our paper and asking an important question regarding practical motivation of protecting distribution.  \n\nLet us first introduce an equivalent definition of LDP that illustrates the operational meaning of LDP. The following equivalent definition of LDP [R1] suggests that an LDP mechanism $p_{Y|X}$ makes it difficult to infer any sensitive information $S$ about a user from $Y$, when $Y$ is provided instead of the user's data $X$. \n\n* **Theorem [R1, Thm. 14]:** A conditional distribution $p_{Y|X}$ satisfies $\\epsilon$-LDP if and only if\n  > $\\displaystyle \\sup_{P_X} \\sup_{S:S-X-Y} \\log \\frac{\\max_{y}\\max_{s} P_{S|Y}(s|y)}{P_S(s)} \\leq \\epsilon$. $\\cdots$ (R1)\n\nAs we can see from the above definition, LDP aims to protect any possible sensitive information hidden inside the user data $X$, and hence the variable $X$ in (R1) should represent **the whole data** possessed by the user that is processed to be sent to the server. \n\nAs the reviewer mentioned, many privacy studies consider the situation where each of multiple users has a single data point, and in this case, $X$ becomes such a single data point.\nOn the other hand, in many practical scenarios, it is more natural to assume that each user possesses multiple data points, e.g., photographs and texts stored in a person's smart phone or multiple medical data hold by a hospital. Accordingly, there have been multiple studies considering the situation where each user has multiple data points. For example, [30] considers a scenario where there are $m \\geq 1$ data points per user, each of which is generated in an i.i.d. manner from an underlying distribution. In this case, it is appropriate to set $X$ in (R1) to be the whole $m$-tuple of the user's data points.\nIn our setting, the user's data is itself a distribution. Hence, the user distribution is in the place of $X$ in (R1). As mentioned in [35], this can be seen as a more general setup that includes situations where each client has multiple data points with variable number of data points, by regarding the multiple data points as the empirical distribution of the multiple data points. \n\nOne naive approach for privatizing multiple data points would be to perturb each data point of the user and send all perturbed data to the server, but it will result in significant privacy leakage due to parallel composition. Hence, developing better privacy mechanisms has gained increasing attention recently to protect the whole collection of multiple data points per user, in the context of not only LDP but also DP.\n\n### Reference:\n\n* [R1] I. Issa, A. B. Wagner, and S. Kamath, \"An Operational Approach to Information Leakage,\" *IEEE Transactions on Information Theory*, vol. 66, no. 3, pp. 1625–1657, Mar. 2020, doi: 10.1109/TIT.2019.2962804.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "jmP2Rcsqbu", "reviewer": "Reviewer_KHbV", "summary": "This paper addresses the problem of sampling under local differential privacy (LDP) requirements, focusing on the privacy-utility trade-off (PUT). It defines the fundamental PUT of private sampling in the minimax sense, using f-divergence as the utility measure. The authors characterize the exact PUT for both finite and continuous data spaces and propose sampling mechanisms that are universally optimal for all f-divergences. The numerical experiments demonstrate the superiority of these mechanisms over existing baselines, showcasing their empirical utilities.", "questions": "1. In practice, would the approximation error of calculating $r_P$ degrade the $\\epsilon$-LDP guarantee to $(\\epsilon,\\delta)$-LDP with $\\delta>0$?\n2. Is the mechanism $Q^*_{k,\\epsilon}$ uniquely optimal?\n3. Is there a typo on line 127: there may be no $r_P>0$ such that (6) **does not** sum to one?", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper presents a novel approach to analyzing the privacy-utility trade-off (PUT) in locally differentially private (LDP) sampling, utilizing f-divergence as the utility measure.\n2. The authors offer optimal mechanisms for both finite and continuous data spaces, given certain assumptions. Figure 2 provides a clear visualization that enhances understanding of the proposed mechanisms.", "weaknesses": "The constant $r_P$ does not have a closed form, requiring calculation through approximate methods. This introduces potential approximation errors that could degrade the privacy or utility guarantees. See question 1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Response to the first question on the approximation error\n\nWe thank Reviewer KHbV for asking a practically important question. We briefly mentioned the effect of the approximation error in calculating $r_P$ on the privacy budget in Appendix F.2, and we considered this effect in the experiment. Let us analyze the effect of this error in more detail in the following.  \n\nConsider the continuous case in Theorem 3.3, and let $q_{p,r}(x) = \\mathrm{clip}\\left(\\frac{1}{r} p(x); bh(x), be^\\epsilon h(x)\\right)$, as in the RHS of equation (13). Suppose we set error tolerances $0\\leq \\delta_1 < 1$ and $\\delta_2 \\geq 0$, and for each $P \\in \\tilde{\\mathcal{P}}$, we find $r_P$ such that $\\int q_{p,r_P}(x)dx \\in [1-\\delta_1,1+\\delta_2]$. Then, we define the pdf of $\\mathbf{Q}^{ * }\\_{c_1,c_2,h,\\epsilon}(P)$ as $q_{p,r_P}(x) / \\int q_{p,r_P}(x)dx$. Since $q_{p,r_P}(x) \\in [b,be^\\epsilon]$, we have $q_{p,r_P}(x) / \\int q_{p,r_P}(x)dx \\in \\left[\\frac{b}{1+\\delta_2}, \\frac{be^\\epsilon}{1-\\delta_1}\\right]$, which implies that this approximated mechanism satisfies $\\epsilon + \\log \\left(\\frac{1+\\delta_2}{1-\\delta_1}\\right)$-LDP. Thus, allowing an approximation error does not require the introduction of $(\\epsilon,\\delta)$-LDP but instead necessitates using a larger privacy budget. Note that to sample from $\\mathbf{Q}^{ * }\\_{c_1,c_2,h,\\epsilon}(P)$, knowing the precise value of $\\int q_{p,r_P}(x)dx$ is unnecessary; it suffices to know $q_{p,r_P}(x)$, utilizing known MCMC methods. In the experiment for the continuous case, we allowed the error tolerances $\\delta_1=\\delta_2=10^{-5}$, and for each given $\\epsilon \\in \\\\{0.1,0.5,1,2,5\\\\}$, we implemented $\\mathbf{Q}^{ * }\\_{c_1,c_2,h,\\epsilon'}$ for $\\epsilon'=\\epsilon + \\log \\frac{1-\\delta_1}{1+\\delta_2}$, ensuring the actual privacy budget matched the initially given $\\epsilon$. We note that there is a typo in Appendix F.2 of the manuscript, which we found after submission. In lines 961-962, the sentence \n\n> \"we modify the value of $\\epsilon$ by $\\epsilon'=\\frac{1-\\delta}{1+\\delta}e^\\epsilon$\"\n\nshould be revised as \n\n> \"we modify the value of $\\epsilon$ by $e^{\\epsilon'}=\\frac{1-\\delta}{1+\\delta}e^\\epsilon$\".\n \nWe also checked the code for the experiment and confirmed that the correct formula was used in the code.  \n\n\n## Response to the second question on the uniqueness \n\nA related question was raised by Reviewer 9St7. Reviewer 9St7 conjectured that a simple randomized response-based mechanism is also  minimax-optimal. In conclusion, we checked that Reviewer 9St7's mechanism is **also minimax-optimal**, meaning our mechanism $\\mathbf{Q}\\_{k,\\epsilon}^{ * }$ is **not the unique** optimal mechanism.\n\nSpecifically, Reviewer 9St7's  mechanism works as follows: for the discrete case, an element is sampled from an original distribution $P$ and then subjected to $k$-randomized response. \nFor the continuous case, the mechanism operates as follows:\n\n* First, toss a biased coin with head probability that tightly achieves $\\epsilon$-LDP. \n* If head, sample from the original distribution $P$.\n* Otherwise, sample from the reference distribution $\\mu$ whose pdf is  $h$.\n\nWe checked that in both setups of Theorems 3.1 and 3.3, this mechanism is **also minimax-optimal** for any $f$-divergences. However, the mechanism proposed in the paper has certain advantages over the aforementioned mechanism. Specifically, let $\\mathbf{Q}^{ * }$ and $\\mathbf{Q}^{\\dagger}$ denote our proposed mechanism in the paper and Reviewer 9St7's mechanism, respectively. Then, we showed that $\\mathbf{Q}^{ * }$ outperforms $\\mathbf{Q}^{\\dagger}$ in a *point-wise* sense, i.e., for any $f$-divergence $D_f$ and any $P \\in \\tilde{\\mathcal{P}}$, we have $D_f(P \\Vert \\mathbf{Q}^{\\dagger}(P)) \\geq D_f(P \\Vert \\mathbf{Q}^{ * }(P))$. The detailed arguments can be found in the rebuttal to Reviewer 9St7.\n\n## Response to the third question on a typo\n\nWe acknowledge that the corresponding sentence might cause confusion. To clarify, the corresponding sentence can be revised  as follows:\n> \"there may be no $r_P > 0$ such that **the RHS of** (6) does not sum to one.\"", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "hS7Zp7tyua", "reviewer": "Reviewer_9St7", "summary": "The paper considers the problem of sampling from a user's distribution under local differential privacy (LDP). Namely, a client has a distribution P in some set of distributions, where the set is known to a data curator. The client wants to perturb P to get Q, such that a sample from Q sent to the data curator satisfies LDP with respect to P (i.e., for any P, P' the probability of sampling a certain outcome differs by at most $e^\\epsilon$ multiplicatively), but also minimizes a given f-divergence between P and Q. The authors give lower bounds on the f-divergence achievable for a given LDP guarantee in two settings, one where the set of distributions is over a discrete support, and another where the set of distributions is over a continuous support, but is lower and upper bounded by some constants times a base measure. They also give an explicit perturbation in these settings that exactly matches the lower bound, i.e. is an optimal solution to the problem. They also discuss why in the continuous setting the lower/upper bound assumption is necessary to get meaningful bounds (in particular, to avoid two disjoint point distributions being in the support), show how to extend their results to a setting where clients only have samples from their distribution, and perform experiments showing that their perturbation achieves better divergence bounds than the previous work \"Local Differential Privacy for Sampling\".", "questions": "* In the discrete setting, we could sample from P and then apply a randomized response to the sample. This seems to achieve the same f-divergence bound (7) in the extreme case where P is a point distribution. This mechanism might be worse for non-extreme distributions, but for the minimax f-divergence this might now matter. Is this mechanism also minimax optimal? If so, in the continuous case is the following mechanism minimax optimal? We sample from P, with some probability p keep the sample, otherwise sample from the distribution with pdf proportional to the base measure h. p can be chosen to be the largest value that preserves LDP.", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "* The paper gives matching upper and lower bounds for a very general form (i.e. for arbitrary f-divergence, rather than a specific divergence) of a natural and important problem of generating private samples with LDP\n* The assumptions for the settings where the authors derive optimal results are well-justified - in the continuous setting, the authors demonstrate that their assumption (10) is somewhat necessary to derive any meaningful results, and the authors discuss how to extend to a more practical setting of clients having samples rather than distributions\n* Numerical results support the theoretical results and make them easier to contextualize, specifically they demonstrate significant improvements in the bounds over the past work", "weaknesses": "* While the proofs of Theorems 3.1 and 3.3 in the appendix are far from trivial, given knowledge of the randomized response mechanism, it's not clear to me that the optimal bounds are as surprising as the authors suggest. See Questions for more detail. \n* The introduction suggests one of the major improvements of the paper over [35] is avoiding the optimality depending on the choice of reference distribution. However, it seems that once we relax reference distribution to measure as the authors do, in both settings the authors consider, there is a natural choice of reference measure to apply the approach of [35] to. It also seems like the results could be retrieved just shifting the lower and upper bounds on the probabilities that [35] uses. While the authors justify the assumptions in the continuous setting that lead to an easy choice of reference distribution, and a lot of work goes into proving optimality of the authors' suggested mechanisms, it's seems both Theorems 3.1 and 3.3 are achievable via a slight variation of the technique in [35], which suggests limited originality/significance for the algorithmic techniques in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Response to the first weakness on alternative mechanism\nWe thank Reviewer 9St7 for raising an interesting point. We are truly grateful for the thoughtful review of our paper.\n\nBefore we discuss about the minimax-optimality of the proposed scheme by the reviewer, we would like to emphasize that even though a simple randomized response-based mechanism provides an alternative achievability result, proving its optimality is a highly non-trivial finding. The exact characterization of the minimax loss requires a converse proof of deriving the **matching** lower bound on the loss applicable to *all possible mechanisms*, not just to randomized response or similar mechanisms. We believe that one of the technical novelties of our work lies in this converse proof.\n\nNow let us discuss the alternative mechanism suggested by the reviewer.  As mentioned by the reviewer, for the discrete case, we can simply sample an element from the original distribution $P$ and apply the $k$-randomized response to that element. This mechanism, which we denote as $\\mathbf{Q}^{\\dagger}_{k,\\epsilon}$, can be written as\n\n> $\\mathbf{Q}^{\\dagger}_{k,\\epsilon}(x|P) = \\frac{e^\\epsilon}{e^\\epsilon + k - 1}P(x) + \\frac{1}{e^\\epsilon+k-1} (1-P(x)).$\n\nWe can design a similar mechanism $\\mathbf{Q}^{\\dagger}_{c_1,c_2,h,\\epsilon}(P)$ for the continuous case as follows:\n\n* First, toss a biased coin with head probability $\\gamma$.\n* If head, sample from the original distribution $P$.\n* Otherwise, sample from the reference distribution $\\mu$ whose pdf is $h$.\n* The head probability $\\gamma$ is determined by $(c_1,c_2,\\epsilon)$ to satisfy $\\epsilon$-LDP tightly. It is given as $\\gamma = \\frac{e^\\epsilon-1}{(e^\\epsilon-1)(1-c_1)+c_2-c_1}$.\n  \nSuch $\\mathbf{Q}^{\\dagger}_{c_1,c_2,h,\\epsilon}(P)$ for the continuous case can be written as \n> $\\mathbf{Q}^{\\dagger}_{c_1,c_2,h,\\epsilon}(P) = \\gamma P + (1-\\gamma) \\mu.$\n\nIt can be shown that in both setups of Theorems 3.1 and 3.3, the aforementioned mechanism $\\mathbf{Q}^{\\dagger}$ is **also minimax-optimal** for any $f$-divergences (here, we suppress the subscripts $(k,\\epsilon)$ or $(c_1,c_2,h,\\epsilon)$ for notational convenience).\n\nHowever, as the reviewer mentioned, $\\mathbf{Q}^{\\dagger}$ performs worse for non-extreme distributions. Indeed, we showed that $\\mathbf{Q}^{ * }$ outperforms $\\mathbf{Q}^{\\dagger}$ for any distribution:\n\n* For any $f$-divergence $D_f$ and any $P \\in \\tilde{\\mathcal{P}}$, we have $D_f(P \\Vert \\mathbf{Q}^{\\dagger}(P)) \\geq D_f(P \\Vert \\mathbf{Q}^{ * }(P))$.\n\nThe above statement is a corollary of a stronger result about $\\mathbf{Q}^{ * }$, which improves the results of [35] in a non-trivial way:\n\n* **For any $f$-divergence**, $\\mathbf{Q}^{ * }(P)$ is the projection of $P$ onto a specific $\\epsilon$-close set, in which $\\mathbf{Q}^{\\dagger}$ also lies.\n\nWe aim to revise the paper accordingly. In particular, we will mention the alternative mechanism that achieves minimax-optimality and provide comments on it in the final version. Thank you once again for highlighting this interesting point.\n\n## Response to the second weakness on comparison with previous work\n\n* First, as described in the response to the first weakness, the proposed mechanism $\\mathbf{Q}^{ * }$ indeed generalizes the approach of [35]: $\\mathbf{Q}^{ * }(P)$ corresponds the projection of $P$ onto an $\\epsilon/2$-ball centered at some reference measure for any $f$-divergence. We would like to emphasize that our work has non-trivial contributions beyond [35] in the following aspects:\n\n  1. Deriving the projection in a closed form for all $f$-divergences is not immediate from [35] which only consider KL divergence. Although the technicalities cannot be fully detailed in the rebuttal due to space constraints,\n  showing general properties satisfied for **all possible** $f$, which may be **non-differentiable**, involves some non-trivial steps compared to [35].\n\n  2. Finding a **right** reference measure is an important step  to characterize the exact optimality. Although we can apply the approach of [35] with an arbitrary reference measure, proving the minimax-optimality with respect to a specific reference measure involves highly non-trivial converse techniques. Our work differs from [35] in that we implicitly figured out the **optimal** reference measure with respect to the minimax loss.\n\n* Second, to the best of our knowledge, the algorithm in [35] to find a KL divergence projection for the continuous case (i.e., MBDE) only guarantees to find an *approximate* projection, not *exact* projection, even if a reference measure is given. Therefore, it is unlikely that a variation of MBDE will retrieve the exactly optimal loss for the continuous case in Theorem 3.3, even for the optimal reference measure we identified. In contrast, the proposed mechanism $\\mathbf{Q}^{ * }$, which has a closed form, achieves the exactly optimal loss both for discrete and continuous cases, thereby eliminating the need for an iterative algorithm for projection as used in [35].\n\n  In more detail, MBDE iteratively updates the candidate $Q_t$ of $\\mathbf{Q}(P)$ based on $Q_{t-1}$ until convergence, employing a soft decision rule (called a weak learner) to distinguish a sample from $Q_{t-1}$ and that from $P$. For $Q_t$ to converge to the optimal one, the accuracy of the weak learner ($\\frac{\\gamma_P + \\gamma_Q}{2}$ in [35]) must approach 1 as $t \\rightarrow \\infty$. However, with the aim of making $Q_t$ as close to $P$ as possible, such accuracy is expected to decrease over $t$. To the best of our understanding of [35], there is no guarantee that this accuracy will converge to 1; thus, we cannot guarantee that MBDE will find the exact projection.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "43FSVNz5xZ", "reviewer": "Reviewer_NxAu", "summary": "Consider the following setting: A public domain $\\mathcal{X}$, a family of distributions $\\mathcal{P}$ over $\\mathcal{X}$, and a mechanism $M$ which give a distribution $P \\in \\mathcal{P}$ releases an element $x \\in \\mathcal{X}$, such that $M$ is $\\epsilon$-pure local DP with respect to the input, that is - the output will have similar distribution for any two distribution inputs $P, P' \\in \\mathcal{P}$. Can we expect the output distribution - that is, the distribution of output elements $x$ given an input distribution $P$ - to be accurate in any way, where accuracy is measured by some $f$-divergence between the distribution of outputs and the input distribution.\n\nAt first, this seems like a hopeless task, since the mechanism has to maintain privacy even against distributions that share no support. Surprisingly, as this paper proves, there is some hope and things are not that bleak.\n\nThis setting was first considered by [1], who proposed optimal mechanisms for finite and continuous domains, with respect to some given reference distribution, for KL-divergence. This paper removes the dependence on a given reference distribution, and instead provides an intuitive algorithm that is optimal for the finite case and does not depend on the choice of $f$. It extends these results to the continuous case, for a family of distributions that are point-wise bounded from above and below by some reference distribution up to scale. Finally, it provides numerical evaluations for the continuous case, which demonstrate the improved utility.\n\n\n[1] Hisham Husain, Borja Balle, Zac Cranko, and Richard Nock. Local Differential Privacy for Sampling. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, pages 3404–3413. PMLR, June 2020.", "questions": "See above", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "This paper is clearly written. Its contribution lays both in its conceptual framing as well as in its theoretical results.", "weaknesses": "Though many of the ideas and proofs in this work are novel, the results can be viewed as a generalization of previously known results as mentioned in the summary.\n\nThough the results achieved in this paper are optimal, they are still quite weak. This is not surprising. As discussed in the summary, the very fact that we can learn anything in this setting is already surprising, given that (in the finite domain setting) the output given two different singleton distributions must be indistinguishable. As a result, the output distribution is heavily skewed towered the uniform distribution.\n\nThe main motivation for this setting is somewhat unclear. Since each user has access to a single distribution, we want to maintain privacy w.r.t. the user's distribution, and so we release a single element, the output is useful only under some assumption on the relation between the users' distributions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer NxAu for thoroughly reviewing our paper and providing valuable comments.\n\n## Response to the first weakness on comparison with previous work\n\nWe agree that a certain part of our results can be seen as a generalization of the previous work [35], as we mentioned in the \"Comparison with Previous Work [35]\" paragraph in Section 3.1. However, we would like emphasize that our work has non-trivial contributions beyond [35] in the following aspects:\n\n*  We prove the **universal** optimality of the mechanism for **all $f$-divergences**, whereas the previous work [35] only considered the KL divergence. Our proof involves numerous non-trivial steps relying on general properties satisfied for *all* $f$-divergences, not specific properties of KL divergence.\n\n* The exact characterization of minimax loss requires a converse proof involving the derivation of the **matching** lower bound on the loss applicable to *all possible mechanisms*, not just to the mechanisms similar to [35]. By proving the matching lower bound that holds for all possible mechanisms, we have established the exact minimax optimality. Note that the previous work [35] does not provide explicit guidance on the choice of reference distribution. More specifically, the performance of their mechanism heavily depends on the choice of the reference distribution. Quite contrary, our work implicitly figures out the optimal reference measure with respect to the minimax loss.\n\n## Response to the second weakness on weak result\n\nWe agree that many existing privacy mechanisms, not limited to sampling scenarios,  can be seen as skewing an original distribution towards a specific distribution (such as the uniform distribution). But the challenging part is determining how and to what extent to skew the distribution to achieve the optimal privacy-utility trade-off (PUT). The significance of our research lies in precisely determining the optimal PUT through non-trivial achievability and converse proofs.\n\n## Response to the third weakness on main motivation\nOur setup has recently gained attention due to its practical applications in generative models. For example, as mentioned in the introduction, [36] uses the private sampling mechanism for fine-tuning large language models.  \nAs mentioned by the reviewer, however, we may consider the scenario where the distributions of the users are correlated. One possible approach is to assume an underlying *distribution on distributions* from which each user's original distribution is drawn, and then infer such an underlying distribution given samples from the users. Also, we can formulate more general problems such as producing a distribution per user or generating multiple samples per user, which we mentioned in the introduction and the conclusion of the paper, respectively. We believe that the problem we considered is a simple yet fundamental one that serves as a stepping stone towards addressing these more general and practically interesting problems.", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for thoroughly reviewing our paper and providing numerous valuable comments. All suggestions have helped us better present our work and delve deeper into our theoretical results. In particular, some comments were especially helpful in improving the paper, and we believe they deserve mention in this global rebuttal, along with our plans for revising the paper.

##  The Effect of Approximation Error of $r\_P$ on the Privacy Budget

Reviewer KHbV raised the following question:

* In practice, to implement the proposed mechanism, we need to find the constant $r\_P$ numerically. Does the approximation error in finding $r\_P$ result in a degradation of the privacy guarantee?

We acknowledge the effect of the approximation error on the privacy budget. We briefly explain this effect in Appendix F.2 and account for it in the experiment. However, recognizing its importance during the rebuttal process, we plan to supplement the detailed explanation of this effect in the revision. More details are provided in the rebuttal to Reviewer KHbV.

## Alternative Minimax Optimal Mechanism 

Two reviewers, KHbV and 9St7, raised a question about whether the proposed mechanism is the *unique* mechanism achieving minimax optimality. Additionally, Reviewer 9St7 proposed an alternative mechanism, $\\mathbf{Q}^{\\dagger}$, conjectured to be optimal as well. Our subsequent work during the rebuttal period confirmed that Reviewer 9St7's mechanism is **also optimal** in the minimax sense. However, we also demonstrated that the proposed mechanism $\\mathbf{Q}^{ * }$ in the paper has an advantage over the reviewer's mechanism in a **point-wise** sense. This advantage arises from the stronger statement that $\\mathbf{Q}^{ * }$ performs a projection onto a specific $\\epsilon$-close set for **any $f$-divergences**. Further details are provided in the rebuttal to Reviewer 9St7.

We believe that these results are worth including in the paper and plan to incorporate them, along with their proof, in the appendix during the revision. In particular, we believe that the property of $\\mathbf{Q}^{ * }$ being a projection for **any $f$-divergences** is a significant advancement over previous work [35], which only considered KL divergence. Although the proof cannot be fully detailed in the rebuttal due to space constraints, we believe that both the property itself and its proof are highly non-trivial contributions beyond [35]. The basic approach is to verify that $\\mathbf{Q}^{ * }(P)$ satisfies the KKT conditions corresponding to the optimization of minimizing the $f$-divergence. However, the main challenges lie in the following aspects, which distinguish this work from [35]:

* We need to show that $\\mathbf{Q}^{ * }(P)$ satisfies **all** the KKT conditions corresponding to **all possible $f$**. This requires relying on general properties satisfied by **all possible $f$-divergences** (possibly **non-differentiable**), rather than specific properties of KL divergence.
* We must also address the continuous space, which involves infinite-dimensional optimization, in addition to the discrete space.

Actually, we had already obtained all the results mentioned in the rebuttal to Reviewer 9St7 for the discrete case before submission. However, at the time of submission, we neither acknowledged the mechanism $\\mathbf{Q}^{\\dagger}$ for the continuous case nor proved that the proposed mechanism $\\mathbf{Q}^{ * }$ for the continuous case performs the $f$-divergence projection. Therefore, we did not include these results in the manuscript for consistency. However, thanks to Reviewer 9St7, we were able to dig into the continuous case and prove the results for the continuous case during the rebuttal period. Accordingly, we plan to include these results in the revised paper. In particular, we will add a discussion on the mechanism $\\mathbf{Q}^{\\dagger}$ as well as a proof that $\\mathbf{Q}^{ * }$ corresponds to the $f$-divergence projection also for the continuous case.

Meta-review: This paper makes the following contribution: it considers a generalization of standard single-point LDP to the distribution version. It measures the utility using $f$-divergene, which removes the reference distribution in prior work. One key result is the establishment of the minimax lower and upper bounds. All reviewers find the results novel and important. I also think it has made some nice contributions and would like to accept it.

Some possible minor improvements for the camera-ready version: As mentioned by the reviewer, the authors may need to discuss the random-response-based alternative method, given its close relation to the optimal one. Another one is the discussion on the parameter $r_P$.
Decision: Accept (poster)