Locally Optimal Private Sampling: Beyond the Global Minimax
Authors: Hrad Ghoukasian
Bonwoo Lee
Shahab Asoodeh
Venue: NeurIPS 2025 poster ()
Keywords: private sampling
local minimax
local differential privacy
functional LDP
Primary area: social_and_economic_aspects_of_machine_learning

Abstract: We study the problem of sampling from a distribution under local differential privacy (LDP). Given a private distribution $P \in \mathcal{P}$, the goal is to generate a single sample from a distribution that remains close to $P$ in $f$-divergence while satisfying the constraints of LDP. This task captures the fundamental challenge of producing realistic-looking data under strong privacy guarantees. While prior work by Park et al. (NeurIPS'24) focuses on global minimax-optimality across a class of distributions, we take a local perspective. Specifically, we examine the minimax error in a neighborhood around a fixed distribution $P_0$, and characterize its exact value, which depends on both $P_0$ and the privacy level. Our main result shows that the local minimax error is determined by the global minimax error when the distribution class $\mathcal{P}$ is restricted to a neighborhood around $P_0$. To establish this, we (1) extend previous work from pure LDP to the more general functional LDP framework, and (2) prove that the globally optimal functional LDP sampler yields the optimal local sampler when constrained to distributions near $P_0$. Building on this, we also derive a simple closed-form expression for the locally minimax-optimal samplers which does not depend on the choice of $f$-divergence. We further argue that this local framework naturally models private sampling with public data, where the public data distribution is represented by $P_0$. In this setting, we empirically compare our locally optimal sampler to existing global methods, and demonstrate that it consistently outperforms global minimax samplers.

Locally Optimal Private Sampling: Beyond the Global Minimax
Hrad Ghoukasian
Bonwoo Lee
Department of Computing and Software
Department of Mathematical Sciences
McMaster University ghoukash@mcmasterrcomm
Korea Advanced Institute Science Technology r righthim@kal ac kr
Shahab Asoodeh
Department of Computing and Software
McMaster University
asoodeh@mcmaseer.com
Abstract
We study the problem of sampling from a distribution under local differential privacy (LDP). Given a private distribution P E P, the goal is to generate a single sample from a distribution that remains close P in f-divergence while satisfying the constraints of LDP. This task captures the fundamental challenge of producing realistic-looking data under strong privacy guarantees. While prior work by Park et al. (NeurIPS'244 24) focuses on global minimax-optimalic across class of distributions, we take local perspective. Specifically, we examine the minimax risk in neighborhood around fixed distribution Po. and characterize its exact value, which depends on both Po and the privacy level. Our main result shows that the local minimax risk is determined by the global minimax risk when the distribution class P is restricted to neighborhood around Po. To establish this, we (1) extend previous work from pure LDP to the more general functional LDP framework, and (2) prove that the globally optimal functional LDP sampler yields the optimal local sampler when constrained to distributions near Po. Building on this, we also derive a simple closed-form expression for the locally minimax- optimal samplers which does not depend the choice of f-divergence. We further argue that this local framework naturally models private sampling with public data, where the public data distribution represented by Pg. In this setting, we empirically compare our locally optimal sampler to existing global methods, and demonstrate that it consistently outperforms global minimax samplers.
Introduction
Differential privacy (DP) [1] is the de facto standard for providing formal privacy guarantees in machine learning. A widely used variant, local differential privacy (LDP) [2], enables individuals to randomize their data their that the output of a randomized algorithm is statistically indistinguishable under arbitrary changes to the input, thereby limiting the privacy leakage of individual's 's data. By eliminating the need for trusted curator, LDP has become particularly appealing to users and companies alike, and has seen wide deployment in practice-including systems developed by Google, Apple, and Microsoft[3-6].
devices before sharing it with untrusted curator. LDP ensures
Despite this progress, much the LDP literature assumes that each user holds only single data point. This assumption is often unrealistic, modern devices routinely collect large volumes of data-such as images, messages, or time-series records [7]. To address this, line of work known as
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

user-level DP assumes that each user holds a dataset of fixed size, with samples drawn i.id. from an underlying distribution [8-16]. However, the requirement of equal dataset size across users limits its practicality.
To overcome this limitation, locally private sampling was introduced by Husain al. [7] and later extended by Park et al. [17]. This framework considers more general setting where clients possess large datasets of varying sizes and aim to privately release another dataset that closely resembles their original data. Each client's 's local dataset is modeled as an empirical distribution P. from which a single private sample is to be generated. Privacy is enforced by projecting P onto a set of distributions called a mollifier- within a certain radius. While Husain et al. [7] construct the mollifier in an ad-hoe manner using reference distribution, Park et al. [17] develop principled minimax framework to identify the optimal mollifier, which corresponds to the worst-case data distribution (namely, degenerate distributions in the discrete case).
In this work, we extend the framework of Park et al. [17] to a public- setting, where each individual also has access a public dataset, represented by distribution Po. From a theoretical perspective, our goal is to move beyond the pessimistic worst-case formulation and instead charac- terize optimal samplers through local minimax lens. From a practical standpoint, this framework is motivated by the increasing relevance of personalized collaborative learning [18-20], in which individual models are trained collaboratively, and the public data may reflect (privatized) information shared by other users. Since real-world data distributions are rarely worst-case, our local formulation better captures achievable performance in practice.
Our local minimax framework aims to identify locally private samplers that minimize the f-divergence between the true distribution P and the sampling distribution, for all P within neighborhood N₂ (P)) around Po. parameterized by constant 7 2 1. This neighborhood is defined via one of the strictest notions of distance between distributions: we say Q E N,, (P)) if Q(x) S <Po(x) and Po(x) S (Q(x) for all x. We will discuss this notion of neighborhood in details in Section 4.
Interestingly, show that the local minimax optimall private sampler under this notion of neigh- borhood is fully characterized by the global minimax minimax-optimal optimal sampler for a restricted class of data distributions. This relationship is most transparent in the context of functional LDP [21]. We therefore first extend the global minimax framework of Park et al. [17] from pure LDP to functional LDP, and then use it to derive the local minimax-optimal samplers.
Contributions. Our main contributions are as follows:
. We characterize the exact global minimax risk of private sampling under the functional LDP framework and derive optimal samplers for both continuous and discrete domains. Lever- aging properties of functional LDP [21], our results generalize the pure-LDP framework
of Park et al. [17] to approximate and Gaussian LDP (GLDP) notions (Section 3). As in their case, our optimal samplers are independent of the choice of f-divergence.
We introduce local minimax formulation to identify samplers that minimize f-divergence over all P E N., for given Po and y 2 1. We then show that this minimax risk is fully determined by the global minimax risk when the distribution class is restricted to neighborhood around Po (Section 4). Building on our global minimax results, we derive closed-form expressions for the local minimax-optinal functional samplers. We further specialize this to express a pointwise optimal private sampler under pure LDP that achieves the local minimax risk (Section 5), enabling direct comparison with the global samplers of Park et al. [17].
We numerically validate our local minimax samplers, showing they consistently- often outterrfo the global samplers of Park et al. [17] across privacy regimes (Section 6). Figure! illustrates that our samplers yield distributions significantly closer to the original under both pure LDP and GLDP.
Related work. Locally private sampling was initially introduced by Husain et al. [7] and later formalized through a global minimax framework by Park et al. [17]. In their work, two fundamentally different families of minimax-optima. samplers were identified: one derived from the randomized
'Exeermment code is publicly available at htops::/githul com/ comm/hraghookas an/ pr private_eee saapeplsssllaaeeeeeeeeeeeeeeee ing. with reproduction instructions provided in Appendix F. For completeness, the code is also included in the supplementary material.

---

Original
Global Pure
Local Pure
Original
Glebal GL.PP
Local GLDP
Figure 1: Comparison of global and local minimax-optimal sampler under pure LDP (s and y-GLDP (v 1.5). Full details of this experiment are provided in Appendix E.
response mechanism, referred to as the linear sampler, and another based on clipping the data distribution, known as the non-linear sampler. They rigorously showed that the non-linear sampler is pointwise better than the linear one. In similar vein, we develop two families of locally minimax- optimal pure LDP samplers and demonstrate that one is pointwise better than the other.
Sampling with public data was recently explored by Zamanlooy et al. [22], who study minimax- optimal samplers in the presence of a public prior. While related, their work differs in key ways: they focus on global minimax formulation restricted discrete domains and linear samplers (i.e.. perturbing the data distribution linearly). whereas we study local minimax problem, support both discrete and continuous settings, and consider arbitrary samplers. Moreover, the role of public data differs between the two approaches. Zamanlooy et al. [22] impose it as hard constraint: their samplers are required preserve the public prior exactly, ensuring that the public data remains unchanged while privacy is enforced only on the private data. By contrast, we use the public distribution to define local neighborhood, which in turn yields a local minimax formulation applicable to general sample spaces. A key implication of this distinction is that in their setting, access to public data does not necessarily reduce the minimax risk, whereas in ours it does.
Private sampling under central DP was introduced by Raskhodnikova et al. [23]. who proposed algorithms for generating private samples from k-ary and product Bernoulli distributions. They showed that sampling can incur significantly lower privacy costs than private learning for some range of parameters. This was extended to broader distribution families [24-26] and multi-sample settings [27].
Private sampling has also gained traction in fine-tuning large language models [28, 29], and is closely related to private generative modeling. However, most prior work in this area focuses on central DP [30-37], assumes single-record LDP [38-41], targets specific estimation tasks [42].
Finally, we remark that local minimax formulations have also been explored in the context estima- tion and distribution learning under DP [43-48]. In particular, Chen and Özgür [43] analyze discrete distribution estimation under LDP by considering neighborhoods around a reference distribution. Similarly, McMillan al. [44] and Duchi and Ruan [45] develop locally minimax estimators for one-dimensional parameters in the central and local models, respectively, while Asi and Duchi [46] extend this framework to function estimation. More recently, Feldman al. [47] utilize the notion of neighborhoods around a distribution in the context nonparametric density estimation. Although these works focus primarily on estimating statistical functionals learning distributions, they conceptually distinct from our setting, which centers on private sampling. Nonetheless, our notion of neighborhood in the local minimax formulation closely aligned with that of Feldman al. [47].
Notation. Let P(x)) denote the set of all probability distributions over the sample space X, and let
C(R") denote the set of all continuous probability distributions on R" For P E C(R"), we denote its probability density function (PDF) by the lowercase letter For any integer
N. we define
[k] = 21, 2, ... k). The notation clip(æ; 81, 82) max (81, min (82, }r} refers the clipping function that bounds x between 81 and 82. The convex conjugate of a function
D C R -
is the function g² IR - (-o0, +oo] defined by g (y) = sup xy g(x) for y E R. We
denote the n-dimensional Laplace distribution with mean m E IR" and scale > 0 by L(m, b). and

---

its density at I E R" by C(x m, b). For the Gaussian case, (m,, E) denotes the n-dimensional normal distribution with mean E IR" and covariance matrix Σ.
2 Preliminaries
In this section, we formally introduce definitions and concepts necessary for the subsequent sections.
Suppose a client holds a distribution P C. P(X) over a sample space X, and wishes to release a sample that resembles being drawn from P while preserving privacy. To ensure privacy, the client applies private sampler Q P - P(X), which maps the input distribution P to privatized distribution Q(P) E P(X). The released sample then drawn from Q(P), thereby preserving privacy while approximating the original distribution. We equivalently view Q(P) the conditional distribution Q P).
Definition 2.1 (Approximate LDP). Let 2 0 and 6 E [o, 1]. A sampler Q P - P(X) is said to satisfy (e, 8)-local differential privacy ((s, 6)-LDP) if, for every pair of input distributions P, P' E P and every measurable set A S X, we have
Q(A ef Q(A P') + 5.
When 5 O. Q is e-LDP sampler [7], also referred as pure LDP. We let 2x. and Q Px denote the sets of all e-LDP and (e, 6)-LDP samplers, respectively.
Definition 2.1 ensures privacy by requiring that the output of the sampler remains indistinguishable under any arbitrary changes in the input. contrast, functional LDP [21] interprets privacy through the lens of hypothesis testing: given two imputs, let P and Q be the corresponding output distributions. The privacy guarantee is quantified by how hard it is for an adversary to distinguish I from Q, which can be framed as binary hypothesis testing problem [49, 50]:
Ho output ~ P vs H1 output ~ Q.
Given rejection rule o x - [0, 1]. the Type I and Type II error rates are defined as
a$ = Ep(ø],
by = - [o]()).
respectively.
Definition 2.2 (Tradc-off function). Let P and Q be probability measures in P(X). The trade-off off function T(P,Q) Q) [0, [0, 1] is defined as
T(P,Q)(u) inf by as S u).
where the infimum taken over all measurable rejection rules Φ.
Notice that T(P, (u) represents the smallest achievable Type error subject to Type I error being u. A function g is called trade-off function if g Q) for some distributions P and Q.
Definition 2.3 (Functional LDP [21, 51]). Given trade-off function [0. 1] + [0, 1]. sampler Q P + P(X) is said to satisfy g-functional local differential privacy (g-FLDP) if for every pair
of input distributions P, P' e P and every [0, 1].
T(Q(- P), Q P')) 2 g(u).
We let 2x,5,, denote the sets of all samplers Q - P(X) satisfying g-FLDP.
Note that functional LDP generalizes both approximate and pure LDP. Specifically, for any privacy parameters (e, 8). there exists a trade-off function 9e.8 such that g is equivalent to 8)LDDP [21, Proposition 3]. This function is given 9e,8 (0)) max (0, 1 - 5 e00, e 5 0)). The case of pure LDP corresponds to the special case == 9r,0- Another notable instance of g-FLDP is
y-GLDP, where the trade-off function is given by (f) = +b ( 0) - v). with &b denoting the standard normal CDF (21,1)]
In order to quantify utility loss incurred by sampler Q we use the f-divergencce between the original distribution P and the resulting sampling distribution Q(P), defined as follows.

---

Definition 2.4 (f diveeregee [52, 53]). Let f (0, + R be convex function with f(1)
= 0.
The f-divergence between P, Q E P()) with P < Q is defined as Dy(P)lQ) = Ee /
AP
aq
The ahove definition can be extended to cases where P < no longer satisfied in Appendix B. Common examples of f-divergences include KL divergence, total variation distance, and squared Hellinger distance. We denote total variation distance between P. Q P(X) by DTv Q). A key instance in this work is the E, -iveereeeee (or hockey-stick divergence), defined as the f-divergence with (() max(t (t- - 7, 0} for 7 2 [54]. This divergence particularly relevant it defines the local neighborhood in our minimax formulation. We denote E,- diveereeee of two distributions P and Q E,, || Q).
Our most general result, covering both continuous and discrete spaces, requires a technical assumption on distributions, stated below and discussed further in Section 3.
Definition 2.5 (Decomposability [17]). Let E (0, 1) and t, u E N with > A probability measure 7l ((X) is (a, t, u) decomposable if there exist sets A A, S X' such that p(A.) a for all i E [t]. and for every E X. the number of sets A; containing is at most u.
Establishing the exact optimal minimax risk in our proof's involves deriving matching upper bounds (the achievability part) and lower bounds (the converse part). For unified proof over general sample space X. the converse part relies on (a, 1) -decomposability: namely, X' contains disjoint measurable subsets, each of measure We note that this mild condition holds naturally for absolutely continuous distributions and for the uniform reference measure in the finite case.
3 Global minimax-optimal samplers under functional LDP
In this section, we study the global minimax samplers under the general framework of functional LDP and derive compact characterizations of the optimal samplers. These global samplers will serve as proxies for constructing local minimax-optimal samplers in subsequent sections.
Using f-divergence as the utility measure, we define the global minimax risk as
R (. Q PeP
inf sup Dj (p Q(P))
As noted by Park et al. [17], this risk becomes vacuous in the continuous setting if the distribution class P is unrestricted. To address this, they consider restricted class of distributions defined as
p PaLcan = (P E C(R") e Ma) S p(x) S c2)(2), Vo E RR).
for a reference function h X 10, oo) satisfying fg-. h(x) dx < co, and constants C2 2 0. This class captures a broad range of practical distributions, including mixtures of Gaussians and Laplace distributions. See the example below and further discussion in Appendices E. and E.2.
Example 3.1. For n, k E N, define P E A.(mm, b) A 2 0, E A = 1, || 11 }
and PN Eim X,N(m, >; 2 Etndd d = 1, ||malla - 1 Here m,, E R and In
denotes the n n identity matrix. can be verified that P.x C Po. 1, and Pe C P Pe-1/b,ee e1/5, where (x) (2 exp [max((.]|=||221/)) and hc(x) f(x 0.
20
Without loss of generality, we assume that fę.. h(x), du = and 0 S ci < < C2. Moreover, for technical ceasons-explaines
Appendix D.2- we also assume that ف-9 E N. This assumption is not restrictive and holds in many practical settings, e.g.. Gaussian mixtures (see Example 3.1). When it is not satisfied, can slightly increase C2 or decrease e₁ to enforce the condition, resulting in superset of the original distribution class, i.e., P C C Po..
While many of our examples focus on continuous domains, our analysis applies more generally to any sample space X', provided the distributions are absolutely continuous with respect to a reference measure μa. In this case, we define Poy.eg. {P E P(X): P < μ, Ci < 4P which we take as the generalized distribution class. Thus, make the following assumption.
du < c2, j--..e.).
5

---

Assumption 3.2. We assume Jgn h(x)) dz = 1 and p(X) = 1 for the classes P Per,ezhh and P Per euapp respectively. Additionally, assume that 0 S c1 < 1 < cz and - E N.
The following proposition shows that additional condition is required exclude trivial samplers. Proposition 3.3. Let be trade-off finctiio. Under Assumption 3.2, if 1 + g²(-ee) >
(o2-c,e") (1-ci)) for all 3 2 0, then Q(P) = P satisfies g- g-FLDP.
In view of this result, we assume throughout that for any given trade-off function g the following condition holds:
33 such that 1 1-9"(-e0) (c2-c1e")(1_1)
Now, we are order state our first technical result.
Theorem 3.4. Let P Per,cu.h. Under Assumption 3.2, the sampler Qº oa defined as continuous distribution whose density is given by
(P))) = Ne x((x)).)(()) + (1- ca. h(x), Xa1.2. = inf e" came1 (I+g"
(4)
820
(1-a) 4ea
satisfies g-FLDP, and is minimax-optimal under any f-divergence, that is
sup Dy(P (PPIIQQ Q .2.hg (P)) - -R(2g- p.g :::: P, PEP
T1 ((2))
12 1 (ri),
(5)
for = 1-(1-c1
and r2
(0g 1) 12.
We note that the non-triviality condition in Proposition 3.3 is equivalent X Xa S 1, which allows a natural interpretation of the sampler ho It samples from with probability Xa 22 and from the reference distribution with probability X² .egg This probabilistic mixture reflects the privacy-utility trade-off: larger x.,, yields outputs closer to P. while sampling from h introduces the randomness required for privacy. The same mixture structure yields a minimax-optimal sampler for the discrete case where X' [k] and p = P((k))
Theorem 3.5. Let P P((k)) for some k E N, and let pa denote the uniform distribution on [k]]
Then the sampler defined as
e ="((ttg"(-=""))
Qi.g(P) = M. (1- Me.))kk Meg inf
920
o 674-1
satisfies g-FLDP, and is minimax-optimal under any f-divergence, that is
sup Dy [P]] Qi. (P)) R R(([)),P. P.f).
PEP
Theorems 3.4 and 3.5 provide optimal samplers for continuous and finite sample spaces, respectively. The next theorem addresses the same task for general sample spaces under the assumption of decomposability.
Theorem 3.6. Lei P under Assumption 3.2, and suppose μ is (a, 3. -)-decomposable
with 1-c1, Then the sampler defined as or (P) Xz.. P P (1 Xe, g)l satisfies g-FLDP. and is minimax-optimee with respect to any f-divergence, where No is defined in Theorem 3.4.
Similar to Theorem 3.6, all subsequent results can be extended to a general sample space. For clarity of presentation, however, we state them in the continuous setting, while all proofs are given full generality.
Having established the optimal sampler for general F-LLP, we present specific instantiations of the result for two widely studied settings: pure LDP and G-LLP First, we derive the optimal s-LDP sampling algorithm by setting 9- Theorem 3.4, as stated in the following corollary.
Corollary 3.7. Let = Pcr.o..h Under Assumption 3.2, the sampler Q" oo defined as a continuous distribution whose density is given by 9 (P) == No + (1 Ne h(z),

---

d'11 with N.1. = (1-c))=+to-11 satisfies F-DF.DP and is minimax-optimal with respect to any f-divergence, that is
sup Dy (PI (P)) -R(O R(2 P.g. P, 1 1-11
- (r2) - (ra))(rr))) f(ri),
T2 12-
(6)
PEP
12 -
for = (1-01)e +ex-1 and 12
(1-21)
22 01
Indeed, by framing s-LDP as special case of functional LDP, Corollary 3.7 reproduces the minimax risk of the optimal e-LDP sampler in [17, Theorem 3.3]. Next, we focus on the v-GLDP as a special case of functional LDP.
Corollary 3.8 (v-GLDP as a special case). Ler P Pe Under Assumption 3.2, the sampler (4) for g = Gy belongs to PR.,P.G. and minimax-optimal with respect to any f-divergence, that is,
sup D2 Q2 (P)) = (QQRx...C.PP11)
PEP
The explicit description of the optimal sampler under v-GLDP is given in Appendix D.6.
As outlined in the introduction, the global minimax formulation under functional LDP serves as the basis for our local analysis. We now turn to the local minimax setting, first under general FLDP (Section 4) and then under pure LDP (Section 5), leveraging Theorem 3.4 and Corollary 3.7, respectively.
Local minimax-optimal sampling under functional LDP
In this section, begin by formalizing the local minimax setting using neighborhood structure induced by the -ivverrgee We then develop a general framework for identifying local minimax- optimal samplers over arbitrary sample spaces.
The local minimax-optimal sampling problem adopts the same structural form as the global minimax problem, with key distinction: instead of selecting the worst-case distribution from the entire space of the general class P, the search is restricted to neighborhood around fixed distribution Po- This reference distribution Po may represent, for example, a publicly available dataset held by an individual or shared collaboratively in a distributed setting. Formally, the local minimax problem under g- g-FLDP is defined as:
R(xx, (Po)),, = inf sup
Dj (PI) QeRx, (PN,(P)
(8)
where N₂, (P)) denotes neighborhood around Po. recently adopted by Feldman al. [47], and defined for any 2 as
(PP) P(x): Pb) ()
(9)
The zero-E, neighborhood generalizes the classical notion of total variation distance. Specifically,
[55, Proposition 4]. Moreover, we can straightforwardly extend this neighborhood to the more general case by replacing (PI) 0 with (PI)P)) < Ç, meaning the likelihood ratio lies in [1/7, with probability at least under Po. This, in turn, enables further generalization any /-divergence with twice differentiable function f. which is a common trick in information theory [56-59]. As in the global case (Section 3), assume N for the same technical reasons. Theorem 4.1 presents the corresponding locally minimax-optimal sampler, connecting the global minimax analysis of Section with the local setting under functional LDP.
for 7 2 F., = 0 implies Drv Q) <
Theorem 4.1. Let Po be a continuous distribution on R". Define (P)) as in (9), and assume (Po) C P. Let Q denote the global sampler from (4), instantiated with parameters e₁ Cg % and h po. We define the sampler Q
(Po)(P))
Q O,,,( (P) Qr()), E
(P),,, otherwise,
7

---

P2
0
1:(%
Po Mr
P QH(P))
((( (Pb)
(P%)
Figure 2: Illustrations of the optimal samplers described in Theorems 4.1 and 5.1. Left: Q (P.)..)) for functional LDP. Right: Q (PP) for pure LDP. Following [17, Proposition 3.4), M, is defined >+1 qhe Po(x) S ((x) s
as M, = {Q e C(R"):
(r+1)e" tte Po(x), Vx E ].).
where P E (Po) is a distribution that minimizes (P(P over all P E (Po).. Then Q* (PD) E 22x P.g and is locally minimax-optimal under any f-divergence, that
sup (y(P O (x,,, Ne (P6)
Theorem 4.1 establishes that the local minimax-optimal sampler for the problem (8) coincides with the global solution in (1) when the universe restricted the N,, neighborhood around Po- In this sense, the global solution presented in Theorem 3.4 directly yields the local solution in Theorem 4.1.
By instantiating Theorem 4.1 with g Is. we obtain e-LDP sampler that is locally minimax- optimal. However, as we demonstrate in the next section, this sampler can still improved pointwise sense.
5 Local minimax-optimal sampling under pure LDP
In this section, we turn our attention to pure-LDP sampling and develop a new framework that fundamentally different from the approach presented in the previous section. Our goal is to identify a sampler that is pointwise better than the one obtained from Theorem 4.1 with 9e- The construction of such sampler presented in the next theorem.
Theorem 5.1. Let Po be continuous distribution RR with density Po and N.((P) be the neighborhood around Po defined in (9). Assuming (y(P)) S P. ler Q (R),N,(P)), be sampler with (P) having density
q(x) clip
7+1 ppp()): p(x);
7 te Po(x),
(7 1)e= 7 -
po(x))
Tp
where p being the normalizing constant ensuring Jzn g(x) de = 1. Furthermore, define the extended sampler ((.N.((P) by
QP(P), E Q:(P), otherwise,
C.N,((Po
where P E (P)) is a distribution that minimizes Dy P') over all P' E (Po).. Then, have (P.) E P. and SUPPEN,(P)) (P (,,, R(2gn (Po),
Similar to Theorem 4.1, the above theorem defines sampler that distinguishes between the cases P (Po) and P & N₂ (P)). In the latter case, both theorems are aligned in that the sampling distribution depends on P. the closest distribution to P within (Po). However, for the case

---

P E (Po). the two constructions differs fundamentally. Theorem 1.1 assigns linear sampler, whereas Theorem 5.1 carefully constructs non-linear sampler tailored to this regime. In fact, this non-linear sampler is obtained by projecting P onto a mollifier Mc; see proof of the theorem in Appendix D.8 and Figure 2 for a visual representation. This projection is carried out through clipping operation, which guarantees that the resulting distribution Q (P) satisfies the LDP constraint while maintaining a close match to the original distribution /' in terms of f-divergence. This approach yields nonlinear transformation of P that carefully balances privacy constraints and utility preservation. It can be verified- using a mutatis mutandis adaptation of [17, Proposition C.5 that the con-ernear sampler pointwise outperforms the linear under the same privacy guarantees; that is, for any 2 and P E Nr (Po)
D(P
|| ((()) S D(P (P)).
In fact, the non non- non-linear sampler outperforms the linear one because is not only worst-case optimal but also instance-optimal: for each input distribution P in our distribution class and any f-divergence D minimizes D (PI[) over all admissible Q satisfying 8-I.DP (see Proposition D.2). In contrast, the linear sampler uses fixed transformation for all input distributions. This instance-specific optimization explains the empirical advantage of the non-linear sampler. As a result, the overall sampler in Theorem 5.1 is pointwise better than the one in Theorem 4.1. This intuition is formalized in the result below.
Proposition 5.2. Let P be the global universe and Po a probability measure on R", with (PP) C for Ny defined as in (9). Let ((P))(P)) be the optimal E-LDP sampler from Theorem 5.1, and Q N, the instantiation of Theorem 4.1 with g =9.- Then, for all P E (P)()).
Dy(PI (,,,1) Dy(PI Og N,,)),
6 Numerical results
In this section, we numerically compare the worst-case f-divergence of our locally minimax sampler against the globally optimal sampler of [17] under the c-LDP setting. Experiments span both finite and continuous domains, evaluating KI. divergence, total variation distance, and squared Hellinger distance across E {0.1, 0.5, 1, Additional results under y-GLDP appear in Appendix E.5 and E.6. In addition, we report complementary results for the continuous case under pure LDP in Appendix E.7.
6.1 Finite sample space
We compare local and global minimax minimax-optimal samplers in the finite setting X' [k]. where the global class is Palobal = P((k]) = Po,r.n. for the uniform measure μ4g, The local neighborhood is defined as Piocal = N1x = P2 7. with 7 = & - 1, ensuring that all local neighborhood assumptions are satisfied and (yr(x) S P(K)). Indeed, both global and local worst-case f f-divergences can be computed in closed form: the global risk is given by [17, Theorem 3.1], while the local risk derived from a finite-space version of Theorem 5.1 (see Appendix F.3). Figure compares the two for k = 20; additional results for other & values are provided in Appendix E.3. The local minimax-optimal sampler consistently outperforms the global Minimax-optimma sampler across all and f-divergences.
6.2 Continuous sample space
In the continuous setting with X' = R, we fix the universe Plocal and evaluate the empirical worst-case f-divergence over 100 randomly generated client distributions Pt...., Pioo E Plocal Each Pj represents a client and is constructed as mixture of random number of one-dinensional Laplace components with scale parameter b = 1; the complete procedure for generating these distributions is described in detail in Appendix E.4.
We define the local and global universes as Piocal = P1/3, 3. Ag and Palobal P1/9, 9, h, where hg is the density of I aplace distribution with mean zero and scale 1. Since Piocal S Pglobal. every client distribution P3 also belongs to the global universe; thus the input distributions are

---

KL
Sq. Hel
0.8
Worst f-divergence
0.8
0.6
2
0.6
0.4
0.4
1
0.2
0.2
0
0.0
0.0
0.1
0.5
1.0
2.0
0.1
0.5
1.0
2.0
0.1
0.5
1.0
2.0
Global
Local
Privacy budget
Figure 3: Theoretical worst-case f-divergences of global and local minimax samplers under the pure LDP setting with uniform reference distribution μrg over finite space (k 20).
identical for both samplers. We evaluate the empirical worst-case divergence of each sampler as max (,(P; Q(P,)). The local minimax sampler follows Theorem 5.1, while the global sampler is the optimal sampler from [17, Theorem 3.3]. As illustrated in Figure 4, the local sam- pler consistently achieves lower worst-case f-divergence than its global counterpart across all f-divergences and privacy levels E.
KL
TV
Sq. Hel
Worst f-divergence
0.08
0.3
0.3
0.06
0.2
0.04
0.1
0.1
0.02
0.0
0.0
0.00
0.1
0.5
1.0
2.0
0.1
0.5
1.0
2.0
0.1
0.5
1.0
2.0
Global
Local
Privacy budget
Figure 4: Empirical worst-case f-divergences of global and local minimax samplers under the pure LDP setting, over 100 experiments on 1-D Laplace mixture.
7 Limitations and future direction
Our main contribution is the development of minimax-optimal private sampler, validated through a series of experiments synthetic data. However, the absence of evaluations on high-dimensional real-world datasets limits our understanding of its practical utility. key reason for this is the computational complexity of our sampler (in particular the clipping function), which poses challenges for scalability in high-dimensional settings. Addressing this limitation- developing more efficient implementations of our samplers or approximate variants, potentially leveraging techniques such as MCMC- is an important direction for future work.
Beyond computational considerations, another important direction for future work is to generalize the formulation the local neighborhood. The neighborhood in our local minimax formulation is defined using the E. -ivvergence: P (P.) if E, Po) E., P) 0, in [47]. A natural exten- sion N.. (b)) == (P E P(x)) E. (P) S and F., (Pol P) < <). The use of Fiy-dieeggence in our formulation is particularly useful, it provides foundation for broader neighhorhood defini- tions. In particular, it can be extended to neighborhoods based on general fdiivergences with twice differentiaale as (Pb)
(P E P(X): (P)) < Ç and (y(P))))) - <} [56-59]. This approach provides principled strategy for characterizing the local minimax solution over the broad and flexible class of distributional neighborhoods (Po). We leave this generalization for future work. Furthermore, this work focuses on the setting where each client releases a single sample. Extending the case of multiple samples per client is natural direction for future work.
Finally, the broader impacts our work is presented in Appendix
10

---

Acknowledgments
This work was supported part by the Natural Sciences and Engineering Research Council of Canada (NSERC).
References
[1] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity private data analysis. In Theory of Cryptogruphy: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265-284. Springer, 2006.
[2] 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, 2011.
[3] Ú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, 2014.
[4] Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnes, and Bernhard Seefeld. Prochlo: Strong privacy for analytics in the crowd. In Proceedings of the 26th symposium on operating systems principles, pages 441-459, 2017.
[5] Differential privacy team Apple. Learning with privacy at scale, 2017.
[6] Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. Advances Neural Information Processing Systems, 30, 2017.
[7] Hisham Husain, Borja Balle, Zac Cranko, and Richard Nock. Local differential privacy for sampling. In International Conference on Artificial Intelligence and Statistics, pages 3404-3413, PMLR, 2020.
[8] Alexander Kent, Thomas B Berrett, and Yi Yu. Rate optimality and phase transition for user-level local differential privacy. arXiv preprint arXiv:2405.1 2024.
[9] Yulian Mao, Qingqing Ye, Haibo Hu, Qi Wang, and Kai Huang. Privshape: Extracting shapes in time series under user-level local differential privacy. In 2024 IEEE 40th International Conference on Data Engineering (ICDE), pages 1739-1751. IEEE, 2024.
[10] Raef Bassily and Ziteng Sun. User-level private stochastic convex optimization with optimal rates. In International Conference on Machine Learning, pages 1838-1851. PMLR, 2023.
[11] Jayadev Acharya, Yuhan Liu, and Ziteng Sun. Discrete distribution estimation under user-level local differential privacy. In International Conference Artificial Intelligence and Statistics, pages 8561-8585. PMLR, 2023.
[12] Ruiquan Huang, Huanyu Zhang, Luca Melis, Milan Shen, Meisam Hejazinia, and Jing Yang. Federated linear contextual bandits with user-level differential privacy. International Confer- ence Machine Learning, pages 14060-14095, PMLR, 2023.
[13] Antonious M Girgis, Deepesh Data, and Suhas Diggavi. Distributed user-level private mean estimation. In 2022 IEEE International Symposium on Information Theory (ISIT), pages 1196-2201 IEEE, 2022.
[14] Daniel Levy. Ziteng Sun, Kareem Amin, Satyen Kale, Alex Kulesza, Mehryar Mohri, and Ananda Theertha Suresh. Learning with user-level privacy. Advances in Neural Information Processing Systems, 34:1 34:12466-111 12469, 2021.
[15] Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. User-level differentially private learning via correlated sampling. Advances in Neural Information Processing Systems, 34:20172-20184 2021.
11

---

[16] Puning Zhao, Lifeng Lai, Li Shen, Qingming Li, Jiafei Wu, and Zhe Liu. A huber loss minimization approach to mean estimation under user-level differential privacy, arXiv preprint arXiv:2405. /3453, 2024.
[17] Hyun-Young Park, Shahab Asoodeh, and Si-Hyeon Lee. Exactly minimax-optinal locally differentially private sampling. Advances in Neural Information Processing Systems, 37:10274- 10319, 2024.
[18] Kaan Ozkara, Antonious M. Girgis, Deepesh Data, and Suhas Diggavi. A statistical framework for personalized federated learning and estimation: Theory, algorithms, and pri- vacy. In The Eleventh International Conference on Learning Representations, 2023. URL http:://openrevies het/foormmid--FuiDNN _44o.
[19] Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 6357-6368. PMLR, 18-24 Jul 2021. URL https: /ptpc//ee/oc........ mlr. ppesssvv399 1wt.i.111hh1.... html.
[20] Michael Zhang, Karan Sapra, Samja Fidler, Serena Yeung, and José M. Álvarez. Personalized federated learning with first order model optimization. In ICLR. OpenReview.net, 2021. URL http://dblp... uni-trier. de/db/ conf httt///lr/cccr////////// haaahh2g
[21] Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 84(1):3-37, 2022.
[22] Behnoosh Zamanlooy, Mario Diaz, and Shahab Asoodeh. Locally private sampling with public data. arXiv preprini arXiv:2411.0877 2024.
[23] Sofya Raskhodnikova, Satchit Sivakumar, Adam Smith, and Marika Swanberg. Dif- ferentially private sampling from distributions. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Infor- mation Processing Systems, volume 34, pages 28983-28994. Curran Associates, Inc., 2021. URL attps://pprocee mww.oeeeeeeddinneeeeeeeeeeeeeee neurips. wwtppppr_.eceeeecceeeeeeeeee wttpe/fllsssaaee/////////////// 2255e26flddae220033886666668--
pdf.
[24] Badih Ghazi, Xiao Hu, Ravi Kumar, and Pasin Manurangsi. On differentially pri- vate 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. URL httpp::/ppooceedaaieee www.iinnnn......eeeeeeeeee.eeeee cttpcc//ppaao. wecppappr_fiiiie www.ss/pppppee////... 444a44882200cbbfffff994555111322 Saw.eeeaaaaaaae-aeeeeaeeeeee Conferonceeeeepeeeeeeeeeo pdd.
[25] Valentio Iverson, Gautam Kamath, and Argyris Mouzakis. Optimal differentially private sampling of unbounded gaussians. arXiv preprint arXiv:2503.01766, 2025.
[26] Naima Tasnim, Atefeh Gilani, Lalitha Sankar, and Oliver Kosut. Reveal-or-obseure: A differen- tially private sampling algorithm for discrete distributions. arXiv preprint arXiv:2504. 14696, 2025.
[27] Albert Cheu and Debanuj Nayak. Differentially private multi-sampling from distributions, 2024. URL
10512.
[28] James Flemings, Mcisam Razaviyayn, and Murali Annavaram. Differentially private next-token prediction of large language models. arXiv preprint arXiv:2403. /5638, 2024.
[29] James Flemings, Meisam Razaviyayn, and Murali Annavaram. Adaptively private next-token prediction of large language models, 2024. URL httppp////peerrreeeeeeee//ooooee fGSEWgRHNZ.
[30] Sofya Raskhodnikova, Satchit Sivakumar, Adam Smith, and Marika Swanberg. Differentially private sampling from distributions. Advances Neural Information Processing Systems, 34: 28983-28994, 2021.
12

---

[31] Badih Ghazi, Xiao Hu, Ravi Kumar, and Pasin Manurangsi. On differentially private sampling from gaussian and product distributions. Advances in Neural Information Processing Systems, 36:77783-77809, 2023.
[32] Hamid Ebadi, Thibaud Antignac, and David Sands. Sampling and partitioning for differential privacy, In 2016 14th Annual Conference on Privacy, Security and Trust (PST), pages 664-673. IEEE, 2016.
[33] Nazmiye Ceren Abay, Yan Zhou, Murat Kantarcioglu, Bhavani Thuraisingham, and Latanya Sweeney. Privacy preserving synthetic data release using deep learning. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 510-526. Springer, 2018
[34] Liyang Xie, Kaixiang Lin, Shu Wang, Fei Wang, and Jiayu Zhou. Differentially private generative adversarial network. arXiv preprint arXiv: 2018.
[35] 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. IEEE, 2020.
[36] Reihanch Torkzadehmahani, Peter Kairouz, and Benedict Paten. Dp-cgan: Differentially private synthetic data and label generation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pages 0-0, 2019.
[37] Yi Liu, Jialiang Peng, JQ James, and Yi Wu. Ppgan: network. In 2019 IEEE 25Th international conference on parallel and distributed systems (ICPADS), pages 985-989. IEEF, 2019.
generative adversarial
[38] Teddy Cunningham, Konstantin Klemmer, Hongkai Wen, and Hakan Ferhatosmanoglu. Geopointgan: Synthetic spatial data with local label differential privacy. arXiv preprint urXiv:2205.08886 2022.
[39] 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):00132, 2023.
[40] Hua Zhang, Kaixuan Li, Teng Huang, Xin Zhang, Wenmin Li, Zhengping Jin, Fei Gao, and Minghui Gao. Publishing locally private high-dimensional synthetic data efficiently. Information Sciences, 633:343-356, 2023.
[41] Hansle Gwon, Imjin Ahn, Yunha Kim, Hee Jun Kang, Hyeram Seo, Heejung Choi, Ha Na Cho, Minkyoung Kim, JiYe Han, Gaeun Kee, et al. Ldp-gan: generative adversarial networks with local differential privacy for patient medical records synthesis. Computers in Biology and Medicine, 107738, 2024.
[42] Jacob Imola, Amrita Roy Chowdhury, and Kamalika Chaudhuri. Metric differential privacy at the user-level via the earth-mover's 's distance. In Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, pages 348-362 2024.
[43] Wei-Ning Chen and Ayfer Özgür. Lq lower bounds on distributed estimation via fisher informa- tion. In 2024 IEEE International Symposium on Information Theory (ISIT), pages 91-96. IEEE, 2024.
[44] Audra McMillan, Adam Smith, and Jon Ullman. Instance-optimal differentially private estima- tion. arXiv preprint arXiv:2210. 15819, 2022.
[45] John C. Duchi and Feng Ruan. The right complexity measure in locally private estimation: not the Fisher information. The Annals of Statisties, 52(1):1 - 51, 2024. doi: 10. 22- 22-AOS2227. URL battps:///o org/10 10///10.11 2214/222-A022222
[46] Hilal Asi and John C Duchi Instance-optimallity in differential privacy via approximate inverse sensitivity mechanisms. Advances neural information processing systems, 33:14106-141117, 2020.
13

---

[47] Vitaly Feldman, Audra McMillan, Satchit Sivakumar, and Kunal Talwar. Instance-optine pri- vate density estimation the wasserstein distance. Advances in Neural Information Processing Systems, 19990066-99111, 2024.
[48] Angelika Rohde and Lukas Steinberger. Geometrizing rates of convergence under local differ- ential privacy constraints. The Annals of Statistics, 48(5):2646-22 2670,, 2020.
[49] Larry Wasserman and Shuheng Zhou. A statistical framework for differential privacy. Journal of the American Statistical Association, 105(489):375-38) 2010.
[50] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference on machine learning, pages 1376-1385. PMLR, 2015.
[51] Bonwoo Lee, Jeongyoun Ahn, and Cheolwoo Park. Minimax risks and optimal procedures for estimation under functional local differential privacy. Advances in Neural Information Processing Systems, 36:57964-5707 57975, 2023.
[52] Syed Mumtaz Ali and Samuel D Silvey. A general class of coefficients of divergence of one distribution from another. Journal of the Royal Statistical Society: Series B (Methodological), 28(1):131-142, 1966.
[53] Imre Csiszár. On information-type measure of difference of probability distributions and indirect observations. Studia Sci. Math. Hungar. 2:299-318, 1967.
[54] Naresh Sharma and Naqueeb Ahmad Warsi. Fundamental bound on the reliability of quantum information transmission. Physical review letters, 11008):88050, 2013.
[55] Jingbo Liu, Paul Cuff, and Sergio Verdú. E.,rrsoolabiiliyy IEEE Transactions on Information T'heory, (365))26292263535 2016.
[56] Yury Polyanskiy and Yihong Wu. Dissipation of information in channels with input constraints. IEEE Transactions on Information Theory, 62(1):35-555 2015.
[57] Maxim Raginsky. Strong data processing inequalities and d-sobolev inequalities for discrete channels. IEEE Transactions on Information Theory, 62()):335 2016.
[58] Behnoosh Zamanlooy and Shahab Asoodeh. Strong data processing inequalities for locally differentially private mechanisms. In 2023 IEEE International Symposium on Information Theory (ISIT), pages
IEEE, 2023.
[59] Shahab Asoodeh and Huanyu Zhang. Contraction of locally differentially private mechanisms. IEEE Journal Selected Areas in Information Theory, 2024.
[60] Igal Sason and Sergio Verdú. f-divergence inequalities. IEEE Transactions on Information Theory, (2((1)):5773-6000 2016.
[61] Andrew Rukhin. Information-type divergence when the likelihood ratios are bounded. Applica- liones Mathematicae, 24(4):415-423, 1997.
14

---

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: The main contributions and scope of our paper are clearly outlined in the abstract and introduction (Section I).
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 not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of work is stated in Section 7.
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]
15

---

All theoretical results in the paper, including theorems, propositions, and lemmas explicitly state the necessary assumptions and are supported by either detailed proofs in the appendices or appropriate 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 if 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 be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
The detailed explanation of of the experiments provide in corresponding section or appendix. Moreover, the instructions for reproducing all figures and experimental results are provided Appendix F.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible 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 NeurlPS does not require releasing code, the conference does require all 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 to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility 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, 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 or verifying the results.
16

---

5. Open access to data and code
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?
Question:
Answer: [Yes]
Justification: The complete code for generating all experimental results is made publicly available at https::/ssc haaa:://gihhii com/hradghoukasiann wwwpiiianpppitteeaeeeeee ing. and for com- pleteness, the code is also included in the supplementary material. In addition, detailed instructions for reproducing all figures and experimental results are provided in Appendix F.
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurlPS code and data submission guidelines (https://nips. cc/
iomeinsssioooooo cessonnolcyy olicy) for more details.
While 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: / //nips. wccppblic/guiceee /ttgggdd///oodeuubnnnnn SuseSuuuumsssioe aasionPoll onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to 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. only subset of experiments are 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 to the paper) recommended, but including URLs to data and code 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 provide sufficient details to implement our proposed sampler and include the code for both the proposed method and the baseline 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 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: Since the main contribution lies in theoretically characterizing the worst-case utility, our experiments are designed to extract and evaluate this worst-case hehavior, rather than assess average-case performance variability.
Guidelines:
The answer NA means that the paper does not include experiments.
17

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
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 or the standard error of the mean.
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 to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in 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: Details on the computational resources and running times for the experiments are provided in Appendix F.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the 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 (e.g., preliminary failed experiments that didn't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http///eurippppppp httpppllctccitasiiieeeeoooppppee
Answer: [Yes]
Justification: Our research conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If 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 (e.g.. there special consid- eration due to laws or regulations in their jurisdiciio))
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 of out work in Appendix G.
18

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness 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 not tied to particular applications, let alone deployments. However, if there is a 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 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 as 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 or unintentional) misuse of the technology.
If there 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).
Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
We do not identify any foresecable risk of misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a 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 to 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 we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [Yes]
Justification: We cite the original paper associated with the source code and ensure that its license and terms use are properly respected.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
19

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com comdaatasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
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 not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent 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. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as 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 as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals 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:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
20

---

Depending on 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.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMS as any important, original, non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https: /tt////eerippppepe http://rppp..ccomeeeeerre/////// ccc.Confeeenncc///25//////////// for what should or should not be described.
21

---

Roadmap of Appendix: The appendix is organized as follows. A more complete notation ta- ble complementing the abbreviated summary the main body-is provided Section Supple- mentary definitions and theorems used in the proofs of our results appear in Section B. Section C presents preliminary results that support the proofs our main theorems, which are then detailed in Section D. Section E describes our experimental setup and provides additional numerical results. Finally, instructions for reproducing our experiments and a discussion the broader impacts of our work are given in Sections F and G, respectively.
A Notation table
Table I provides comprehensive summary of the notation used throughout the paper, comple- menting the abbreviated overview in the main body for the reader's 8 convenience.
Table I: Important notations used in the paper
Notation
Description
P(X))
Set of all probability distributions over sample space X'
C(RR)
Set of all continuous probability distributions on IR" Probability density function (PDF) of P e C(RR") Shorthand for 21,2,... ..,....... k} for k E N uniform distribution over finite sample space [k]
p
[k]
pk
clip(a; $1, s2)
Clipping function: max(s1, min($2. x}}
Convex conjugate of function 9
L(m.b) b)
n--imensional Laplace distribution with mean m E IR" and scale b Density of the Laplace distribution at a E R n-dimensional Gaussian with mean m E IR" and covariance matrix Σ Density of the Gaussian distribution at IR"
L(x m. b)
N(m, E)
Qx.P.e
Set of s-LDP samplers: Q -
2x.8,
Set of (c, 6)-LDP samplers: Q: P(X)
2x
Set of g-FLDP samplers: Q P P(X)
(11 112
f-divergence between Bernoulli distributions with Pr(1) Aı and Xa
B
Supplementary definitions and theorems
B.1 General definition and special cases of f-divergence
In this appendix, we review the general definition and special cases f-divergences which are important in this work.
Definition B.1 (General case of f-divergence [60]. Let P and Q be probability measures, and let be dominating measure of P and (i.e., P. < μú e.g., P P + Q), and let p dQ The -hiveriee from P to Q is given, independently of by
dP and
q dp
(y(1)) = / gf (2) dp.
(10)
where
f(0) lim f(t), 7---
(11)
0f = 0,
(12)
0
0f a = lim tf ( = lim f(u) 00000
0.
(13)
Popular examples of o fddieergencess include KL divergence (f(() 1 log (), total variation distance (f(1) = 1 squared Hellinger distance (f(1) = (vi- 1)3,, and -iveeergee (f(1) (1-1)2). We also formally define diveereree for f(t) = max(t 7, 0} for 1.
22

---

Definition B.2 (E, divergencc [54]). Given 2 1, for two probability measures P,Q E P(2)) with
P Qu the E,- -iveeregge
7, _ / -app -1--1- 1).
Q) Ee
max
dp dq
For more extensive list of f-divergences and their properties, we refer readers Sason and Verdú [60].
B.2 Measure-theoretic assumptions
The appendices assume familiarity with basic measure theory and real analysis. Throughout the main paper and the appendices, we adopt the following conventions. For every sample space X' o-algebra on X' is assumed to given implicitly. Unless stated otherwise, we use the discrete o-algebra when X' is finite, and the Borel o-algebra when X' = IR... Whenever we refer to a "subset" of X, we mean a measurable subset. Similarly, the notation the term "continuous distribution" refers specifically to distribution that is absolutely continuous with respect to the Lebesgue measure.
X' always indicates that measurable. Finally,
B.3 Supplementary theorems
This subsection presents two well-known results that we will use in proving our main results. Theorem B.1 (Data processing inequality). Let M be conditional distribution (Markov kernel) mapping from X y. Given distributions Pi, P2 E P(X), and their fushaforward measures Q1, Q2 E P()) through M, the following inequality holds for any f-divergence:
DP I| Pa) 2 Dy(Q1 || Q2).
Proposition B.2 (Proposition of Dong al. [21]). A function 9 [0,1] + [0, is trade-off function if and only if g convex, continuous, non-increasing, and g(x) S x ffo x E [0,
C
Preliminary results
Lemma C.1. Let p be (fixed) distribution over some output space X. For each 0 S X S define
sampler Q2 by
Qx(A P) XP(A) (1 M(A), for any distribution on X and event S X. Suppose there exists 0 5 A1 I 1 such that Qx, is (E,6)-LDP. Then for any X2 E A1), the sampler Q2 is also (e, 6)-.D..
Proof. Fix X2 [0, and let P. p' be any two distributions on X. We need to show that for every event A,
Qx P) S e
6.
Because d2 < Å₁. there is E [0, such that
A = B
Then, for all events A,
Qx PA P) de P(A) (1- (2-12) BAI + [1- B A11 M(A).
Recognizing that À P(A) + (1 x1) is Q (A P), we rewrite:
Q₂ (4 P) 8Q. P) + [1-3]u(A)
Similarly,
(A P') BQ., (A|P') P') (1A))
Since Qx, is (E,8)-LDP, we know
Qx (A S e (A| + +
23

---

Multiplying both sides by / 2 0 and then adding (1 - () ((A), we obtain
Q (A | P) + (1 - 3) ((A) S Be Qx (A P') + B6 + () (1-B))(()) m(A).
But the left-hand side above is exactly Qx₂(A P), so
Qu (A1(A (AI S 3 Qx (A P') + 36 + (1 (1- (A)))
On the other hand,
ef Qxa(A| e (Qx P') + (1 (B)) Be -ex (A P') + (1- B) M(A).
Hence,
e 22 P') + 8 = B6 -B P') + (1- ((A) +
is enough to check
e Qx (A P') 38 (1 (() & Be QB, P)) + -1- M(A) + 6, which simplifies
38+ + (1 - (()) 1 (1 3) (44)+ +
Rearranging,
(1 - (1-3) e S 8 3).
Since 1 1- S O for E 2 O, and ā 2 O, this inequality holds trivially (the left-hand side is at most O, while the right-hand side is nonnegative). Thus the overall chain of inequalities is valid, and we conclude
(A P) s et Qx)(A)P) + 8, VP,P', event A.
Hence Qx is also (E,6)-LDP.
Now, we first restate the normalization condition and introduce the non-triviality assumption for (c, 8)-LDP before stating the next proposition.
Normalization condition:
m(x) 11 0550 < 11< cz.
(14)
Non-triviality condition:
8 < (eg - (1
(15)
Ci
Proposition C.2. Consider the following optimization problem:
R R(QxxP,e.:PP. qe@x PEP
inf sup
(P
(16)
Let p- -P Po such that the normalization condition (14) and the non-triviality condition (15) hold and q=a E M. Suppose that μs (a,, 3. 1) decooppoaable with 1-9 -0-c1
Define
(1
C e + C2
-
(1 0e + 02
P1
C2
C1
1 1-
C2 Ci
ca-1 8 e
1-c1
Then, the optimal value of the problem (16) is given by
(( = 1 r1 f(12)
+ 12 1
f(r1).
(17)
12 ri
12 71
Moreover, the sampler Q (P X dH, with X [I [1 -1
belongs to the
class P.e5 and is minimax-optimal under any f-divergence Dy. That is,
sup D ( (P)
R(.x P.f)
(18)
PEP
24

---

Proof. We first show that if the non -n-triviality constraint (15) does not hold, then the identity sampler Q'())= P satisfies (E,6)-LD and has the trivial minimax risk zero.
Suppose we have (1=-a)=)\_aa)
Let C be a measurable subset and P, P' E Ponica 62
1=e1 0 S p(A) 02
e + ('A)
IV IV IV
((E + +d -c2((A
(Gre -c2)(1 c1) + +8,0
min
C2 - c1
0.
1-0L (A) 2
C2-c1¹
é P(A) + - P(A)
IV Iv
((A) -- Pl-9))
qe u(A)+ + (1-a - ((A)))
(GIE -
(9 c1((1 -c) -1+ +8
C2
(Gte 02) c1)
+
02 C1
0.
Therefore, for 8 >>>>>>>>>> (0a-ord"\1-a)) Q'(P) E ex. and the minimax risk is trivially zero. In the
remainder of the proof, we consider the non-trivial case of 5 < (11m))0(000))
Step 1: Proof of Q² is probability measure
In this proof, we show that Q defined by Q7,(() = No P+ (1-11 X2,) is a probability measure. Since P and μ are probability measures, we have
Q P(x) (1 - ((() X3 + (1 \و,) =1
Assumptions 0 0 c1 < 1 < C2 and 8 (1-0))\11-c)) imply
02-61
e 13-01 θ 1
e ---01 l-c
(02-01e')
5,5 (1 1 6 + C2
1-
C2
61
1.
e
+ 02
2 0. It suffices to show that for every measurable Therefore, for any A C X. we have (2,(()) subset A C X, we also have
(t)(A) < 1,
which implies Q7 is a probability measure. We proceed by bounding:
(A) = XCsP(A) + (1 ((A)
Ni -a (1-1 + (1- ((A)
(1- (1- ((A) 11 ci)
-1) -))
(1- d1e + (c2 c1)6 - (1-c))
+
I ciee + -1 [1 di + 1
(1 ce + C2² -
[1 ci + -1
The inequality in the second line uses the fact that
P(A) < 1 ei (1 ((A))..
25

---

This follows from the definition
Pa == { (PEP(X): P& as df
c u.e.).
du
and the fact that for PE PEPoLCan Po
e1 ((A9) < P(AS) = 1 1- cI ((A) 2 1 1- P(A9) = 1 ci (1 - m(A)) 2 P(A).
of 1-918-1 8-1 And the inequality in the fourth line comes by plugging X2,5 (1-e1)e+to221 into the equation and the fact that ((A) S 1. Hence, Q is indeed a probability measure.
Step 2: Proof of Q2 E Qx.P.0.8
Now, we want to show that Q is an (s, 6-LDP sampler. For this purpose, we have to show that for each measurable set A S X' and any pair of probability measures P and P', we have:
ef eQ (P) + 5 (P') 0.
First, suppose m(A) S
1-G1, We then have:
c2
c (Nix + (1 ((A) + 5 - (1i + (1 (1- (()))(A))
2 (E ((A) + (1xx)))u(AA) + 8 (2is (1 - -xEs))(AA))
(Ais(efs -c2 + (6-1)) u(A) + 8
C2 -1
C1 8 (((A) + 8
1-c1 C1
2 0.
Next, suppose u(A) 2 1-91 Then:
0g-01
(1()((A) + (1- X X()))((A)) + (XE. + (1- ((,))
2 o (ML,C))(A)) + (1- (1))))(((A)))))))))))))))))))))) +5 (1 +a)((A) + +(1- (225)))((
-)A;;))) (ef -1)(1 (1 ) ((A) 11 +6
(1(1-(1-a))))
(1- (1-1(1))55)) ) -1 (1(1)c)) +8
1 1-9) 11 c1) +
2 (E - 1)( (1 c 3)
62
(e 1)(1 - () - c)
(1- )e + (e2 - -)8 (1 c1)
(1 - e + 02 - +
(1 - ---eee- + 0 -
8(1 (e 1) (02 .8 +
- de + 02 -1
0.
Therefore, in both cases:
e (1 +
-
2 0,
which establishes the (E, 6)-DP criterion for every measurable set A. Hence the sampler is (s, 6)- LDP.
Step 3: Proof of optimality, lower bound
In this part, we show that:
1 - r1 f(rz) +
12 1
f(r) S P...
T2 r1
12 1ı
26

---

To this end, we need to show that for each Q E e we have
1 - T1 f(r2) + 12 f(ri) - sup (s(P))((P) PEP
1
When -- N, let Q be (s sampler, i.e, Q 2 P. Define
c1 C2 C1
t: - e N.
Since is (a, 2/ ddccompposab with E N. we can find disjoint sets A Ar S X' with u(A,) a. Define P. probability measure by dP. du Pt defined as:
p((x) c2) (1))
where
Ln,(z)= {
if A., otherwise.
Let Q == Q(P:). We aim show:
min Q.,) < e² + (t 1)8
By the (e,8)-LDP property, for every i >> 1, we have
(A,) + (A))
Thus,
(QI(A)) +6) N Σ (A.).
Note that
(UA,) Ai + (1. (1--1)
= ())((A))))(&Q)
é (Qi)
i=2
S E9 (1
Qi (Ai)) + (1- 1)6
S e (1 min Qi(Ai) + (t 1)6,
and
(A1).) 2 (1 - 1) min (A,).
Therefore,
min (A4) v e + (t 1)8
e -t
Rewriting in terms of a, we have
min Qi(A.) < aet + (1 a)o
(19)
ac +1
Next, we lower bound the worst-case f divvergeeec:
sup (P sup DJ (cza Q(:):)),
where (21 || A22) denotes the f-divergence between Bernoulli distributions with Pr(1) A and Ag:
1-11
Df A2) = def N
+ (1
(1-12)
(1-
27

---

For each A,, the push-forward measures of P. and Q, by the indicator function 1,, are Bernoulli distributions with Pr(1) = a and Q; (A,), respectilly... By the data processing inequality (Theorem B. I), we have:
(₂(P:(QQ)) 2 DJ (czallQQ
Therefore, we have:
sup Dy ()(P(((P)) sup Dy Q+)
PEP
iE|d
Dj (cza Q;(A:))
sup <E[|]
ac + (1 - a0
2 Dj
C2a ||
ae 1 -
where the inequality in the last line follows from (19) and the fact that if 0 S (1-+( ae-+1-a S C2a and DJ (>1 || A2) decreasaing in X2 E (1,
(ca-c)e(((-ee) then 02
(1--))e(((101)) then +1'+(1-))á Here is the proof that if 8 < 02-01
ac*+1-a S c20r
aC + (1 a:j
(1- --)e + (c2 - 118
ae 1
oi + 02 -1
[02 ((==
(1 - 9 + (02 - 1)
<
(1 - og)E + C22 -1
a
(02 )e (c2 -1)(e2 cE6
c96
02 - C
(1 ce + C2 -1
22 c1)
C2 - C1
c
Therefore, it suffices to compute
DJ (22a ||
ar' ae' +1--a6) It can be shown that ac=+1-a
ae + (1 a:)
ae + (1 - a)o
ac + 1 (1-0)0
a + 1 - a
DG C2a
f c2a aE + + - a1- a)o
ae + 1
+ (1 a) 6)
ac + 1 - a
ac + 1 f (1(1 - a)
(1 - 1l-a((1= 8)
(1 - ajee + (c2 - 1)5
C2 (1 - ai aie + 02
f
(1 aee 002 1
C2 - 4
ق2=2 ++11=00 8 e
(c2 1)(1 - 8) f
a (1 de + -
+
(1 9) ) + t -
12 Ci
1- d
Defining
C
(1 q ee
+ 02 1
01 )e + 02 1
r =
12
C2 C1
1-8 8
e
02-18 8
we have
(1 (1-G)
C2 - Ge - 9-9 6
1- r
(02 [1 8)
(c2 1) (2 - caee ---a 8)
(c2 - -c)
6 + c2=1
28

---

Thus
1 - n
(1 - e + (02 - 1)8
r2 1
(1 0 +
- 1
(02 - 1)(1 -
12 1l
0 e + C2
Hence, for each Q E 2x 8,
we have
- T1
(r2) + 1
f(ri) sup (y
22 1i
r2 71
PEP
Step 4: Proof of optimality, upper bound (achievability part) In this part, we show that:
R R(QxPr.. p.f) 1 1- f(12) 12 1
12 T1 f(r1).
12 - 11
To this end, we need to show that for each P E P, we have:
Dy Q2 (P)) -
rl f(22) + r2 f(ri).
T2 T1
dQ x('
Fix P E P. Letp
and g
We first claim that
du
du
((x) ((x)
r1 S
12
for μ-almost every x E &. Indeed, we have
p(x)
p(x)
<(x)
()() + (1 );,6)
which an increasing function p(x) 2 as long as X S
Now we show that if s
(oa-cre")I1aa) then X; (1-q)e=+o2
ex 4-000- 5-1
1 S 1.
E" + e- 8 1
X
I-c
g)e + 1
e w-a
(9-0)e((160))
T-c:
02-01
(1 de + 02
6 + 02 CI6- -
(1 - -- + C2 1
1.
Since p(x) is bounded between ei and C2 it follows that
Ci
p(x)
02
(20)
1 + - x
(x)
02 + +11 X2,6)
for p-almost every I E X. From the premise of the proposition, we have
e + 2--18 8-
X =
(1 ee + -1
can be shown that:
C1
(1 - 61 )E² + 02 -
< < 02 (1-ci)e- + 02
p(x)
(1 ())
9(z)
e
02-1 1-o1
8
which concludes
r1 <
12
((x)
for ju-almost every x E X. To finalize the proof of the achievability part, we need the following lemma.
29

---

Lemma C.3 ([Theorem 2.1][61].. Let P.Q E P(X). Suppose that P and Q are both absolutely
continuous with respect to a reference measure μ on X. Assume that there exist T1. 12 E with
dQ satisfy g(x) > 0 and dr and q du Sn < r2 such that the corresponding densities p dp
p(x)
S for p-almost every x E EX.
q(x)
Then, for any f-divergence D it holds that
1 - r1 f(r2) + r2 f(r1).
Q)()) V
r 1l
12 -1
Lemma C.3, directly shows that for each P E P, we have:
1- 11
12 1
(y 02, (P))
f(r2)
f(r1)
r2 T1
T2 11
for
C1 TI
(1 -ie + 02
02
(1 cj)e +
T2
C2 C1
2
6
8
Corollary C.4 (g FLDP as special case). Let P P2. Under Assumption 3.2, suppose the
reference measure μ is (a, : decoopposalee with 1-01 Then the sampler
02-61
aa (P) == ea P+ (1
Ne. )
(21)
belongs to the class 2x, and is minimaa-optimal with respect to any f-divergence D,, that is, sup D2 (PI) PEP
Co (P)) (( P.f):
(22)
where
e + c 8
X 02ile
(1 (1-c1)e* + -
Proof. From Theorem 3.6, we know that the sampler
Q Qc (P) = Xenreagee P+ (1 Nevergee
for A...a. defined as
c- (1 + g2,8 (- I-c
02.9.. = inf
820
(1 0 + C2 -
belongs to the class 2x. a..s fore, it suffices to compute D5.5 (-ef) and then solve the minimization problem.
and minimax-optimal with respect to any f-divergence Dy. There-
direct comparison of the three affine pieces shows
1 8 - 6
0205 1-8 1-
#141 #+1 < 5
e e - 0),
(e.
(23)
0,
1 8 0
-00
otherwise.
For any R. (v) intervals of (23). Denote the corresponding optimized values by
sup (0y 5 splits naturally into the supremum over the three 0se51
Si(v) := sup {By (1 5 - e
oses 24
S2(v) = sup 14 505--6
{0y- - e 8 - -]}
Sa(v) sup
{0y}.
1-85051
30

---

We now optimize over each sub- uub-interval.
(i) Interval 0 I 0
1-6 e1+I
Writing the objective as + - (1 (1-6), 6), it is linear in Hence
(11 -),
v -ce
Si =
1
- e0 + yy - 1), y -e.
(ii) Interval 1-5 e+11 S S 5. Here the objective equals (y + 6= e- 5 (1 6). Thus
1 ò e +1 (y 1),
y S -
S2(v)
(1 5)y, y 2 =
(iii) Interval 5 S 0 S 1. The objective is simply y0,
(1 6) y,
y < 0,
Sz(y)
y y 2 0.
We now take the overall supremum.
Comparing S2, S3 on the four regimes
(-oc, -et), [- -e- [-6-5,0, [0, xc) gives
8), =<-E; -
(y) 1),
-e S S -
(v) = (.))
e + 1
(1 y,,
-
y:
y y20
Step Solve the infimum to obtain
X 62.
From
+ 69-01
(1+ ge,((-e -1
inf 920
I-c
(1 - E) jel + 02
Hence, we only need to know the value of -eB S - for given E 2 0. i.c.
We know -ca < -1 for B 2 0. Therefore,
(1 - 8)z
-e S =ee
g2.(--0
5
8 - 1)), -Ea S - S -1
e +
It follows that:
e + 6-66
1-
المع 1- - 5)
8 12-01 8 - 8
I-c1
Xas.r1.9.5 = -min
inf
inf 3E(0.5]
82c
- 1
(1- + 02 -
e + 62 - 1- (1 8)
min
(1 0: e + C2
Ca
Since 4-9 E N and 02 > 1, it follows that 1-27 > 2, which in turn implies + 2 2. Now we
want to show that if (j + 2 2, then:
e + 02 8
(1 8)
2
2+
11 - G e +
-1
1 C1
31

---

Because e1 < 1 < 22 and e" 2 1, the denominator (1-11) -1)e" + is strictly positive, so we can multiply both sides of the inequality by without changing the sign. Set
A (1 ai ee
02 - 1 0.
The claim is equivalent to
(1 - ci) - - c1)8 2 1 (1- (1-11-
-6) 6) 2
(54T A.
Bring the left-hand side the right and factor out (1 - -):
2A
A (1 6) + - [1 - ()) (E - 1) + (c2 - c1)6]
2A
(c2 c1)(1 8) - -1 6)
ef e
2A
(1 (1- (c2 +1
Since 1-6
222200 0, we only need to prove
(c2 - ci( +1) 2 24.
Substituting A gives
(02 - cIje + (c2 - c1) 2 2(1 - cije + + - 1).
Rearranging, we have:
(c2 1 1) 0.
Because - 12 for every e 2 0, the last inequality holds precisely when 0₁ + 02 2 2 0, i.c. when C + C2 2 2. This is exactly the hypothesis, the desired inequality is proved and we have:
6 + co-C 8
I-e
(1 cae + 1
Step 3: Optimality proof
Following Theorem 3.6, for the obtained value of 7e.. the sampler
Q Ss.se (P) = Xa P (1 X oe )
belongs to the class 2x, a..s and minimax-optimal with respect to any f-divergence D,, that is,
sup Dy (P Co (P)) R(xx. P,f). PeP
D Proofs of the main results
D.I Proof of Proposition 3.3
Proof. Based on Proposition 6 in Dong et al. [21]. for a trade-off function g. sampler is g-FLDP and only if is (s, 1 + g" -) for all 0. In the proof of Proposition C.2, showed that if 8 > (ca-c1e" )(-ca))) then the identity sampler Q'(P) P satisfies 8)-LDP and has the o2-ci
trivial minimax risk zero.
Suppose the non-triviality condition (3) does not hold, i.e., for any 2 have:
1 1 (-ce) (02 ()ee(( e))
C2 C1
In this case, the trivial sampler QP()) = P satisfies (a, + g" (- (-L for any e 2 and therefore satisfies g-FLDP and has the trivial minimax risk zero.
D
32

---

D.2 Proof of Theorem 3.6
Proof. In this proof, we assume that the non-triviality condition (3) is satisfied.
The proof of this theorem is directly based on Proposition C.2. Accordingly. the global minimax- optimal sampler in Theorem 3.6 builds upon the minimax-optimal sampler proposed in Proposi- tion C.2. The lower bound in the optimality proof of Proposition C.2 relies on the existence of disjoint sets A1,..., Ar, of the optimality proof hinges on the (a, 1 1) d:cccooposaabllttyy of μ., where -- N. This 1-61
each with measure (u(A,) a, where
In fact, the converse part
technical requirement motivates the assumption + T-o1 E N in Assumption 3.2.
Step 1: To propose a g-FLDP sampler Q21.c2.4.9
From Proposition C.2, we know that for each pair (e, 8), the sampler
( Xe P + (1 X,,s
with
c + 9-6
N2,
(1 (1- c1) e + C2
is minimax-optimal in the class 2x,P,e,
Next, based on Proposition 6 in Dong et al. [21]. for a trade-off function g. a sampler is g-FLDP if and only if it is (e, 9² (- )-DD for all E 2 0. Consequently, if we set 0(s) 1 + g- and define
Q ste) (P) = M2,0(e) P + (1- (1sdE,(te)11)
then by Proposition C.2, we have Q E xx,
We then use Lemma C.I, which states that if Qx, = X1 P + (1-x1) is LDDP for
0 S \ I 1, then for any d2 [0, 21). the sampler Qx₂ = X2 P (1 >2) is also (c, 5) -LDP.
Therefore, if we define
e
1+ g-
(- e0) -
inf B20
(1 -1- -1) ea + (c2 - 1)
this guarantees that the sampler
Qi on P) = Xoneoa P + (1- Xo..ea.))
is (e, 1 + g (-c)))) for all 2 0. Note that the non-triviality constraint (3) guarantees that
there exists an 2 0 for which 1 + g-((=e") < (0=-a)e"((aa)) and therefore X x.. I 1. By Proposition 6 of Dong al. [21], being (e, 1 (=(0(()) LDP for all E 2 0 is exactly the definition of being F-FL.P. Hence, Q oo. is indeed a a g-FLPP sampler and therefore belongs to 2x, P. This completes the proof of the first step.
L-DP
Step 2: To prove the optimality of Q2
Proposition 6 of Dong al. [21] tells us that if we set
5(E) = 1 + g'(-)
then for every 2 O we have inf Q @x.F. PEP
sup
2
inf
sup (,(P)IQ(P)).
(24)
Q QeQx PEP
On the other hand, define the sampler
X P (1 X 22.02.9)4
where
e + o-
g7( (=(=)) ea) -
I-c
Xa
inf
c2
(I (1- e + C2 -1)
33

---

Let Eg be the value of E that achieves this infimum. The infimum is attained at a finite value of because, if we define
E + a-a (1 1
hg(5)
(1-c)e + (02 - 1)
then we have
(0) lim lg(e).
5-+00
Together with the continuity of (E), this implies that the infimum is achieved at some finite Eg.
To establish the continuity of (e), we note that both the numerator and denominator are continuous functions of and the denominator is never zero. To verify that the numerator is continuous, it suffices to show that 9" is continuous. This follows directly from the definition the convex conjugate and the fact that the original function is continuous on the compact interval [0, and takes values in [0, 1] (see Proposition B.2). Hence,
(1 (1+9(- - I-61
+
q-a
c1)
By construction, Qa belongs to the Ex. From Proposition C.2, we know Q Qeyerin is minimax-optimal Pep
Hence,
sup Dj (p(P Qc (()))
inf QE Pe Beg) PeP
sup
()(P))((P))
(25)
PEP
Finally, combining (24), (25), and the trivial inequality
inf QE@xPa PEP
sup ()(PI)(()) I sup Dj (Pl Q (P))
PeP
we conclude:
sup Dj P O Q (
inf
sup ()(P))(P))
QElxP.aaac) PEP
P
(ex P.f)
inf qERx PEP R( PIT.
sup (p(P Q(P))
which completes the proof of the second step.
Step Computing the optimal value of R (2 g. P.f)
It follows from the previous step that in order to compute R R( f), it suffices to compute
R P.F).
From Proposition C.2, we know that
R R(
5l.y) P,I) P.I)
1 1- f(r2) + f(r1)
1
r2 ri
122 ri
for
(1 - C1 ee +
(1 - ci + -1
C2
8(Et)
T2
C2
c c-1 2-18((e))
I-c 8(Et)
We now compute ii and r2 terms of No
For 8($))
1 1 g-( (-e have
(1 c1) S + -1
(1 - ci + +02 -1
12
C2 C1
g* (-)
C2 Ci
(1 + (-((()))
34

---

Moreover, we have
④ a--
1 + (-
1-9
No 121. =
(1- (02 1]
Let 0 : Eb, 8(E)) = + +0((-0)) we have
8+ + C2 8(Eg) -
C1
(26)
(1 c1) + (c2 - 1)
Therefore,
C1
(1 01) + 02
11
C1
1 ((Eg)
From (26),
(02 - -a (1)
1 (1 - ci) 02.00. 02.9
(1 - c1 + (02 1)
Hence
C1
r1 =
1- (1
1
Similarly,
C2
(1 2 + 02 -
12
02 C1
0 +
2 8(c7)
Ci
Using (26) again,
(02 1)
+1=
02 C1
0 + 1-1
5(5))
(1 - 01 0 + (C2 - 1)
I-c
Thus
C2
=
(02 1) +1
In conclusion,
(e Mey P,S) = R( R(2xx P,
1 1- f(2)) +
T2 f(ri),
11
for
C1 and
C2
r1 (1 C1 01.0219
r2
(c2
1)
10,00100 .229
+
D.3
Proof of Theorem 3.4
Proof. Based on Theorem 3.6, we define p. = Por.ez, under Assumption 3.2. Moreover, suppose is (a, deccmoooosos with a 1-61, Then, the sampler defined as
o (P) Na P (1 Xc 1
satisfies g-FLDP and is minimax minimaa--optimal with respect to any fddivergence, where X At
c2,0 is defined
e+ 47 (-+00
inf 820
Theorem 3.4 is special case of Theorem 3.6. Below, demonstrate this reduction explicitly.
Recall that in the setup of Theorem 3.6, for general sample space X, the universe Po is defined as
dP
P Porozu = PEP PEP(N): : P p. 9
S c2, u-a.c.
dy
35

---

In the setup of Theorem 3.4, X' = R", and P is defined as Par. = {P E C(R²) cjh(x) S p(x) S c2h(z), Vx E RR).
Let denote the Lebesgue measure on R". We have R", and P Pa,ez,h Po where J < and 2x h. Therefore, Q% 2 Q og..haaa
This is because for each P E P with corresponding PDF p(x), the chain rule of the Radon-Nikodym derivative gives:
dP
dP
dp
dP
p(x)
(x)
(x)h(x).
dx
du
dx
du
remains to show that μ is (a, 1 a' 1) decoompsabble for a 1-tt. From Assumption 3.2, we know that t o2-01 N. Therefore need to show that μ is (2, t. decomposable.
Since μ < the function + ((ooo,, s] x 1=-1) continuous. As s + -o,, this measure tends to 0, and as + oc, it tends to 1. By the intermediate value theorem, for each E [t], there exists threshold s; E R such that
u((-o0, s; x R=-1)= = ai.
We then define the sets A1 (-00, -1|x and for 2 set Ar (st-1, st) x R=-1, These sets satisfy the requirements of (t f, decoomossabilityy Therefore, μ is indeed (1. t, 1) decomposabbe, completing the proof.
Therefore, Theorem 3.6 contains Theorem 3.4 as special case. Under Assumption 3.2, the sampler og defined as a continuous distribution whose density is given by
(1+9 (-e" (27)
4 (P) = No (e).).g(()) + (1 - Xa. h(x), Ven.eu.g
inf $20
satisfies g-FLDP and is minimax-optimal under any f-divergence. That is,
sup (y(P O h2 (P)) = -R(2 p.g. P, = 1- 11 f(22) + T2 ((11), PEP
r2 11
for r1
and
I-
D.4 Proof of Theorem 3.5
Proof. From Theorem 3.6, we know that if P P ea. is defined under Assumption 3.2 and j (a. 3. deccoppossleee with a og oa-c1"
1-9 then the sampler Qo.. (P) = Na..22.9 P + (1
Xoner.)) belongs to the class 2x,F, and is minimax-optimal under any f-divergence Dy; that is,
sup D2 ( oo = ((.x.Fg..P11) PEP
In this case,
e + I-a (1 + (-
X Na.
inf B20
(1 (1- ) + C2
can be shown that:
dP
P((k)) Po Po PEP(()): P&p,,
ph:
05
pk-a.e.
duk
Consider the following setting:
p P(k),, = [k], C =
C2 c k,
# == pb:
where μts is the uniform distribution on [k]. In this case, we have 9= k N, and μe is (a, 1, 1) -eccompsabble with }.- Morcover, for this specific instantiation, it can be shown that for s 2 0,
a
+ g" (-6)) (c2 - --ee) a)) (I)(1)
=1 1.
C2 C1
k
36

---

This comes from the definition of the convex conjugate and the properties of the function g:
Vs 0
-1s 50 O,
and hence,
1 1- SL.
Therefore, all conditions of Theorem 3.6 are satisfied and Theorem 3.5 is a special case of the more general case Theorem 3.6. Hence, the sampler Q (P) == No. P + (1 X p belongs to the class Q P and is minimax minimax-oppiimll under any f-divergence D,; that is.
sup (P Qk. (P)) R( (1), P.J),
PEP
where Ag. is the optimal solution to the following optimization problem:
e² k x((+g((-))))1
X inf 320
e + k-1
D.5 Proof of Corollary 3.7
Proof. Corollary 3.7 follows immediately from Corollary C.4 by setting 8 = 0. With this choice, we have Is = 9e.us thus the proof identical. Moreover, in the proof of Theorem 3.4, the continuous case of Corollary 3.7 can be shown to be special instance of the more general result stated in Corollary C.4. For completeness, a brief proof sketch is provided below.
Step 1: Find 0
1,
if < -e5,
(v)
if 6 < y S -e
(28)
+1
y.
if y -
Step 2: Solve the infimum to obtain
X21.22.9
if + 02 <2
(e++1x(-e)> e'
X 02.92
(29)
if + t 2 2.
(1-q))
Since -a-01 E N and 02 > 1, follows that 00 2 2, which in turn implies ei + 2 2. Hence:
e -
Xe ee
Step 3: Optimality proof
Following Theorem 3.6, for the obtained value of 02 the sampler
Qer.rap.ss (P) = Xa P (1 X )
belongs to the class Q &x.a. and is minimax-optimal with respect to any f-divergence Dy, that is.
sup ( Q* Og (P)) = R R(2 x.. P.F).
PEP
Therefore, we have:
sup (P(PI PEP
(P Q ea (P)) -R(Q= p P,S)
1 1- ri
f(r2) + T2 - f(r))
T2
12 r1
for r1 =
10-a))=+tzz and 12
62
(1-c))e*+ee
62
c-a
The optimal value of R(2Rm, p.g. P.J) is obtained directly from Theorem 3.4 by substituting
e
Ne (1-9)e +
37

---

D.6 Proof of Corollary 3.8
Proof. From Theorem 3.6 we know that for
e
1-e1 (1 G c)(-e")) -1
X2
inf
#20
(1 cI e C2
the sampler (4) for g = Gy belongs to 2 and is minimax-optimal with respect to any f-divergence, that is,
sup PEP
Q2. = R,
Now, we compute G- shown in Corollary of Dong et al. [21] that
1
V 1
()(y)= = y 2
log( (og(-y))
log( (e(--y))
2
When y = -e
(-e²))
- e ②
v
8
- 1b
v
+
3
2 1)
2
Therefore, we have:
1 e
(-6 - 2) $
(- + :))
I-c
inf No.
$20
11-6) 1e + 02 -1
- 2 - 2))
e
+
9-9
1-G
inf 920
(1 c e 02 - -1
D.7 Proof of Theorem 4.1
Proof. Step 1: Lower bound
In the first step of the proof, we establish lower bound for the local minimax objective function
R R (2xx.... (P)), as follows:
inf sup QERx... (EN,(P))
(PI]
inf M PEN,(P6)
sup
(p Q(P))
R( (Po)
(30)
The inequality in the second line follows from the fact that any sampler Q P - P(X) in 2x. also belongs to Qx.N,(P)).9- The third line is by definition of the global minimax risk in (1) when the universe P is restricted to (Po).
Step 2: Upper bound
We now construct sampler that achieves the lower bound. Specifically, we aim to find sampler Q* (P,) E Qx such that
sup (P RR(x.,N, N,(o),,))
(PN)(P))
Observe that the neighborhood (P6))) aligns with the class P- P Paros defined in Theorem 3.6:
Perozu = { PEP(X): PEp, a 5 dP S 02 u.a.}
du
38

---

(P.(P) = { PEP(X):
1 dP
dPg (z) st Vx E 2
7
By substituting C1 4, 02 7, and μ Po. we obtain Par = (Po).
Additionally, since y E N, it follows that 1-a I- E N, satisfying the integer condition in Theorem 3.6. The (a, d. 1)ddcoooooos of Po with स+ also matches the requirement that is (a, a 1) -ddeoomposabble with a
1-6
62-01
Therefore, all the conditions Theorem 3.6 are satisfied. Thus, the optimal sampler Q corresponding to (c1, C2. 14) = Po achieves
(P()) R(Qx.MAPSs (P()) (EN,(P))
sup
Since Oy defined only on (Po), we extend it to the larger domain P by defining:
a (P,) (P) (Q)P), E
(P),, otherwise,
where E (Po) a distribution that minimizes Dy P') over all P E (P)))).
By construction, Q (P,), E Px and for all P N- (Po), have:
(p (,,, (PN)(P))
sup
sup PEN.(P))
Dy (y (P(P)
Hence, we obtain the upper bound:
N, ., (P),))
QERxPPo (PN)(P)) ()(P))((P)
inf
sup
(P Q N,,, sup
PEN)(P)
((xx,N (P))
(31)
Combining equations (30) and (31), conclude that
R NT - N. (N
R
Note that this proof is stated for general space A' and a general universe P = P -ea. It extends directly to the continuous case with X' R and P Pa, Pai following the same reduction argument used in the proof of Theorem 3.4.
D.8 Proof of Theorem 5.1
Proof. let the global minimax formulation under s-LDP be defined
((xxFs::P1) = inf sup ()(PIQQ(P)) QE@x, PEP
(32)
Under certain assumptions, formally defined in Section 3, Park al. [17] derives the optimal sampler and optimal value for the optimization problem (32).
Step 1: Lower bound
In the first step of the proof, we establish a lower bound for the local minimax objective function R (x (Po), f) as follows:
39

---

R(2x Ny(oo),
inf
sup
()(P)Q(P))
QECxP, (EN,(P))
inf (PP PEN,(Po)
sup
()(P))((P)
(33)
The inequality in the second line follows from the fact that any sampler Q - 2x. also belongs (x.,. The third line is by definition of the global minimax risk in (32) when the universe P is restricted to (Po).
Step 2: Upper bound
We now construct sampler that achieves the lower bound. Specifically, we aim to find sampler Q (.N) 2x,P, such that
Dy(PI) (P)) = = N,(, (EN)(Po)
Let sampler Q (P6) P(t) be an optimal sampler for the global minimax problem (32)
where the universe P restricted to N,()). In other words, Q achieves
R R(xx,,,PR)ee (P())..))
sup (EN)(
Since Q defined only on (Po). we extend it to the larger domain by defining:
Q Ox,,(ro) (P) = [Q)(), if P (Po),,
(34)
(P)),, otherwise,
where P (Po) a distribution that minimizes Dy P') over all P' E Ny
By construction, Q (P,) E Exx and for all P E N, (Po). we have:
sup (PN)(P)
Q, (PN)((P)
sup
Dj (p(P]]
Hence, we obtain the upper bound:
inf Q.Qx.*.
PEN,(U6) (p(P))(PP)
sup
Dj Q (2N,(()) PEN,(Pb
sup
(Q (P)...)..
(35)
Combining equations (33) and (35), we conclude that
R (x
R (Gx.M,
Step 3: Local minimax risk in a closed form
Under the same non-triviality assumption as Park et al. [17], for the pure LDP case we assume & log(r); otherwise, the identity sampler becomes the trivial local minimax-optimal sampler with zero minimax risk.
Consider the case where 2log(>) < In this case, for any P1 E N,,))), we have (x))/22(x) < <fe hence easily observe that the sampler Q defined as Q(()) P
40

---

for all P E (Po) satisfies E-LDP and R (P, = 0. Since Q is defined only on (Po), we extend it to the larger domain P by defining:
(P,,, (P) = (P),, E
(P),,, otherwise,
where P (Po) a distribution that minimizes Dy P') over P' E (Po) We conclude (.
0. Therefore, to exclude trivial samplers we assume
E < 2 log(?).
In order to obtain the local minimax risk under e-LDP, we refer to Theorem C.4 in Park et al. [17].
Theorem D.1 (Theorem C.4 of Park et al. [17]). Let P Pes,er. be of distributions such that the normalization condition (14) holds, and suppose μ is (a, a decomposable with 1-61 Define
c2-61
(e 1)(1 91) + 02 ci ci Then, the optimal value of the problem (32) is given by
71
b
be
R(Qx.F.:
1- r r2 -1 f(22) +
1 -1 f(r1).
Furthermore, the sampler Qi er. defined below is optimal solution to problem (32) under any f-divergence Dj. For each E P, 1e (P) = Q be a probability measure Q < μ, such that
dQ dp
1 dP
(x) clip
- rp du
(x): b, be
where up the normalizing constant ensuring that
f
dQ
dp(x) 1. du
Observe that the neighborhood (Po) aligns with the class p P Per defined in Theorem 3.6:
dP
Pe Poy.aa.e PEP(X): P&m, 1,
S u-a..
dp
(Po) PEP(())
1 dP
Vo E x x (z) S9
7 dP
By substituting c1 7. 02 = 7, and μ = Po. we obtain Por (Po)..
Additionally, the (a, 3,4 i)ddecomposability of Po with a = I also matches the requirement that (a, 1 decoomoopsllee with 1-9, c--
We now aim compute the closed-form expression for
R NN
By the equivalence Por. = (Po) and Theorem D. applied with (c),02,11) (2.7.P)). we
have:
R R(Qx,,,(S)),,,,(PP..)) N.)))
1- f(r2) +
f(rz),
12 11
r2 -
where
7-2 (e5 1) (1-1 ) + ee
7+1
1 e + +
r2 7
7/6- + 7) e + 1)
T1
7
77 +1)'
ber
Since
R R(O, (e - R (ex.M,CessseeNN((()))..
the optimal minimax risk is obtained.
41

---

Step 4:
Optimal sampler
From the upper bound proof of the theorem, know that the sampler (P,) defined in (34), is an optimal sampler, provided that
sup Dy ()(P)(((P)) (R (Po)
Therefore, it suffices to construct a sampler Q (PP) + P(2') that belongs to 2x,N, and satisfies the above equality.
By applying Theorem D.I with (c1, c2 11) = (4,7, 7,, we obtain the following definition for such a sampler. For each P E (Po), define Q:(P) = Q, where Q is a probability measure satisfying Q < Po and given by
dQ aP (z) clip
- Tp dP
1 dP
7+1 7
(z);
7+ E e
7 7
with rp denoting the normalizing constant ensuring that
de dPo(z) 1. 7P
We extend this sampler function over all of ((2) by defining
(,,, = Q:(P), if (P)))),
QP),,, otherwise,
where P (Po) a distribution that minimizes (y P') over all P' (.).)).
Then Q (R)) E 2x.P.e and the following holds:
sup Dy (P, = -R(ex... (PN)
Note that this proof is stated for general space X and a general universe p P ez extends directly to the continuous case with X' = R" and P Pare following the same reduction argument used in the proof of Theorem 3.4.
D.9 Proof of Proposition 5.2
Proof. To prove this result, we need to define preliminary samplers and the universe set. Let
Parc P PEP(X): as dP
S c2 mae.
du
Define sampler Q Qu E 2x as follows:
For each P P, Q er (P) = Q is defined as probability measure such that Q < and
aQ (x) = clip dp
dP (z); be
rp dp
where rp > a constant depending on so that J d2 ddd(x)) =
Proposition D.2 (Proposition C.8. of Park al. [17]). For any P Perioun and any f-divergences Dr, we have
Dy (P Qr oz
inf QEPo,
Dy
for
C2 - C1
(e
+ +)
42

---

We want to prove that if we define the neighborhood as
(Pu) = {P P(X): (P (Po P) = 0}:
and let Q denote the optimal sampler from Theorem 5.1, and let Q be the instantiation of Theorem 4.1 with g - ge- Then, for all P E (Po),
Dy Q+) S ()
Note that this inequality is equivalent the condition that for all P (Po))).
(p || O N,,, V (2 || N,,)),
which is the ultimate result we want to prove in this proposition.
Therefore, suffices to show that for P Parezr (Po),,, we have Q Qei and that 0g E PPbybe spc
It follows that for c₁ 4 - 7, and μ Po. we have the equivalence P (Po).. For this instantiation of P. uu.. u the optimal sampler Q Qerezmme for input P is defined as probability measure such that Q < Po and
dQ
(1
1 dP rp dPb (z): bet
dPo (I) clip
where
7 1 b (e 1) 1) + e +
2 +
This is exactly Q the optimal sampler from Theorem 5.1. Thus, it remains to prove that Q
Po.ber,Po Pb for b = 2+1 +"
Combining Theorem 4.1 and Corollary 3.7, we obtain
7(65 -1) Qg. (P) = Ng. P (1 )g.) Ag. (1- (1 +7-1 (4 - 1)(e +7)*
6 1
Recall that
Po,ber == { QEP(()) Q &o.
dQ
b b5
S be
Po-ac..
dPo
and
(P6) PEP(Z)) P < Po.
1
<
dP
S n Poac..
7
dPo
Therefore, if (Po), we have
dQ; dPo
dP
yr
Na. dPo
+ (1 - -
It follows that Q < Po and
Xx
dQ² g:
(1 x²x s
< 9xx= 2
+ (1- (1-)))) Po-a..
7
dP
Equivalently,
72 c²
dQ y/ <
72 -1) + (x - 1)(ee +7)
-e
(7 ( ()- +7) +
Po-a..
(7 - 1)(c5 +7)
dP
( 1)(cs +7)
As result,
72-1 1
dQ't
(72 1)ee
<
Po-a...
(7- 1) + +7)
dPo
( - 1)(e +7)
Or equivalently,
7+1
dQ f/
(7 + 1)e
<
Po-a.e.
e +
dPb
e +
This shows that Q E Po,ber, and completes the proof.
43

---

E Detailed experimental setup and additional experiments
E.1 Mixture of Laplace distributions
Proof of Pc C P. 1/0, at/2, b2 (Example 3.1)
Let the mixture Laplace distributions with fixed scale parameter be defined as
k
PC.
Σ de A(ms, k X 0,
Σ > =1 |mell S
where L(m, b) denotes the nz-dimensional Laplace distribution with mean m I2" and scale parame- ter > O. We aim to show that
Pe Pe-1/h e//b, hhr
where he is the density of the zero-mere n-dimensional Laplace distribution with scale parameter b. The density of an n-dimensional Laplace distribution with location m E" and scale is given by
|| - ml11 ) E R...
((x | m,,) b)
(2b)a exp
b
Now, fix any m E R" such that || S 1. Then for any x E R", we have the following bounds:
|20||2 |mm|l
|
mil1
|| [1 + |mmll
b
| 1
1
mil
| +1
b
Exponentiating both sides, get:
||0|||
+
(-11a || mll1
(-
||x/|1
-
exp
S exp
S exp
b
b
Multiplying by the constant
(26)m we obtain:
1/b (2b)m
||||||
et/b
|
exp
b
< C(x m. <
(2b)
exp
b
which implies
e 1/h [(x 0, 6) S [(x m, b) s 1/b C(x 0.
For any distribution P Pe Pc, we can write
k
p(x) = Σ A f(x m4
Since each m, satisfies ||m/]la I 1, the above inequality applies to each mixture component. Thus, for all x I.,,
e 1/b C(x 0.b) <
Mc(x m, S 1/b L(x 0,
1=1
Defining po(x) L(x 0, b), we conclude that for every P E Pe,
p(z)
116 1/6 <
1/6
Va E R"
Po(
which confirms that Pe S 2/
Experimental details of Figure 1
The original distribution is mixture of four two-dimensional Laplace distributions, each with scale
parameter and means (1, 0), (0, 1), (-1, and (0,-1) -1), respectively, with equal weights That is, the input distribution is given by
44

---

Pinput
[(mi, 2),
i=1
where the m, are defined as above. From Example 3.1, we know that Pinpur E P. where
h p = X D) 0,
X = 1, |mlll $
and furthermore, P C PP-1// e hg- where hg denotes the density of two-dimensional Laplace distribution with mean zero and scale parameter 2.
For = 2, we define the local and global minimax universes as
Piocal P
P222.h Az and Pylobal P 6.6.
These universes chosen such that Plocal C Polobal, Pinput E Procal iP global, and the ratio Ga-e1 N,
I-o;
as required by Assumption 3.2. Moreover, we note that Pa-1/0 e he S P 2.2, 2,
Ag* ie., the condition in Assumption 3.2 is achieved by slightly adjusting the bounds and 02 using floor and ceiling functions.
We evaluate the performance of minimax-optimal samplers on the input distribution under two LDP settings: comparing local minimax-optimal samplers with global minimax-optinn opptimal samplers under both y-GLDP and E-LDP. In the pure-LDP setting, we compare the global minimax-optinng sampler of Park al. [17] with the local minimax conimax-optimal sampler from Theorem 5.1 for 1. In the y-GLDP setting, we compare our global minimax-o optimall sampler from Corollary 3.8 with the local minimax-optimal sampler from Theorem 1. using the special case g = G. with
1.5.
Under both settings, Figure demonstrates that the local minimax-optimal sampler better preserves the input distribution compared the global minimax-optimal sampler, given the same level of privacy.
E.2 Gaussian mixtures
Proof of PN S. Po, 1, (Example 3.1)
let PN = { (Ex 1 Aa((m; I²In): Ai 2 0, Σt \; = |mmlle < 13.
We want to show that
PN C Po, 1. where (x) (2x02) exp [0xx(0
20
Fix a component centre m E IR" with ||m||2 S 1. Its Gaussian density at x
N Nm.orI, [x]
(2mo22)m/2 exp
2x
By the triangle inequality,
|| mll2 2 ||0/||2 - ||re|la| 2 max ||0||2 - 11,
because ||m||2 < Squaring and dividing by 20 yields
- 26
S exp [mxx(0,|==|1a-111)
exp
Multiplying by the common normalizing constant (2TT²)--i) gives
Nm [x] < hw(x), Vx R."
Now take an arbitrary mixture E N: 1n) E PN. Its density is
b p(x) = Σ
A Nm (x).
45

---

Because each component satisfies Nm, -r, [x] S (x) and the weights obey X; 2 0, Σ, A =1, we have
0 p(x) S hx(x))
Yar E R
byy- Therefore P E 1o 1, by- claimed.
worth noting that hy not a probability density. In order to make hw a valid probability distribution, we normalize it by its integral and define
= / hxr()) dx, and h(x)
hv(())
c2
Accordingly, we have 1a, Po,
E.3 Finite sample space numerical results under pure LDP
Experimental details of Figure 3
We compare local and global minimax-optimat samplers in the finite setting X' = [b]]. where the global universe is defined as PPyoosl = P((k) = Po. with Pa denoting the uniform distribution over [k]. The local neighborhood is specified as Piocal = NG = P 7. where 7 2 consistent with the finite-space version of Theorem 5.1.
1,
For the selected values & E {10, 20, 100). is easy to verify that y E N, and the uniform distribution 14 is (a, a -e-doooopssbble, where
2
C2
C1
7
Therefore, the decomposability condition in Theorem 5.1 is satisfied, and we can apply its finite-space version by setting = [k].
The local minimax risk is then given by
1 1--1 T1 [(22) + - 1
R ((1,))P(H))) N,
12 12-1 f(ri),
12 m
where
7 (e 1)(1
7+1
1 e + r1
7 7(05 + 7) be c + 1)
12
7+ 6
y
7(7 + 1)'
On the other hand, the global minimax risk is given by [17, Theorem 3.1]:
e c + k
e
k k-1
R(Q P(
e c-+k-1 f(0).
Therefore, in Figure 3, we compare the theoretical worst-case f-divergence losses achieved by the local mitimax-optiiml sampler and the global minimax opptiall sampler:
R (((()),(())) Ny(m),.) and R(Q))) P()
Additional numerical results
We replicated the procedure used in Section 6. to generate Figure 3 but now with sample sizes k = 10 and k = 100. As shown in Figures and and comparing with Figure 3, the local minimax sampler consistently attains smaller worst-case loss than the global minimax sampler across different 8 values. Also, the performance gap decreases for larger values of k.
E.4 Experimental details of continuous sample space
In the continuous setting with X = R. we fix the universe Plocal and evaluate the empirical worst-case f d-iveegeence over 100 randomly generated client distributions P P100 Piocal Each P.
46

---

KL
TV
Sq. Hel
Worst F-dvergenen
2.0
0.8
1
0.6
LL
1,5
0.6
0.2
0.5
0.2
0.0
0.0
0.0
0.1
0.5
1.0
2.0
0.1
0.5
1.0
2.0
0.1
0.5
1.0
2.0
Local
Privacy budget e
Figure 5: Theoretical worst-case f-divergences of global and local minimax samplers under the pure LDP setting with uniform reference distribution μ4 over finite space (k 10).
KI.
TV
Sq. Hel
1.00
Worst rdivnrgenen.
0.8
0.75
3-
0.6
0.50
0.2
0.1
0.5
1.0
2.0
0.5
1.0
2.0
0.1
1.0
2.0
Global
Local
Privacy budget E
Figure 6: Theoretical worst-case f-divergences of global and local minimax samplers under the pure LDP setting with uniform reference distribution μæg over finite space (k 100).
represents a client and is constructed as a mixture of random number of one-dimensional Laplace components with scale parameter b = 1. The full generation procedure is described below.
We define the mixture class of Laplace distributions with fixed scale parameter as
Pe
X C(m,, b) k [K], A 0.
Σ 11 |m;l $1
where L(m, b) denotes the one-dimensional Laplace distribution with mean m and scale parameter b >> 0. To prevent an unbounded number of components in each mixture, we impose an upper bound K on the number of Laplace components per client.
Each Pj Pe is generated by randomly selecting k, >Ú and m, follows: First, sample k from a Poisson distribution with mean kg. and set min + 1, K). Then, sample each mi, my independently from the uniform distribution on [-1, 1J. and sample weights (A1,..., Ax) from the uniform distribution on P([)). In this experiment, maintain consistency with Park et al. [17], we use K 10 and ko 2.
We define the local and global universes as
Piocal Pi Pi/a,, hg and Polobal P1,9, /9,00 99999,94 Ag
where lg denotes the density of the Laplace distribution with mean zero and scale b 1. We evaluate the empirical worst-case divergence of each sampler using the maximum
max Dy Q(P))).
jE[100]
The local minimax sampler is instantiated from Theorem 5.1, while the global minimax sampler corresponds to the optimal sampler from [17, Theorem 3.3].
E.5 Finite sample space numerical results under GLDP
In this section, we adopt the same experimental setup as Section 6.1 to evaluate the worst-case f-divergence of the local and global minimax samplers under v-GLDP constraints. To this end,
47

---

follow the same procedure using the same global and local universes. However, the computation of minimax risk differs: for the global minimax risk, we use the optimal value corresponding to the optimal sampler characterized in Corollary 3.8, while for the local minimax risk, we instantiate Theorem 4.1 with g = Gy (both the finite sample space version of the results).
KI.
TV
Sq. Hel
Warst Fdivergenee
0.8
11
1.5
0.4
1.0
0.4
0.2
0.0
0.0
0.0
0.1
0.5
1.0
2.0
0.1
0.5
1.0
2.0
0.1
0.5
1.0
2.0
Global
Loral
Privacy budget v
Figure 7: Theoretical worst-case f-divergences of global and local minimax samplers under the y-GLDP setting with uniform reference distribution μt over finite space (k: 10).
KL
TV
Sq. Hel
Worst rdivergenne
0.4
0.4
0.1
1.0
2.0
0.1
1.0
2.0
0.1 1.0
2.0
Global
Local
Privacy budget
Figure 8: Theoretical worst-case f-divergences of global and local minimax samplers under the
μ-GLDP setting with uniform reference distribution μy over finite space (k: 20).
KL
TV
Sq. Hcl
Worst f-dvvergenos
0.8
0.75
3-
0.6
0.50
0.4
0.25
0.00
0.0
0.1
0.5
1.0
2.0
0.1
0.5
1.0
2.0
0.1
0.5
1.0
2.0
Global
Local
Privary budget v
Figure Theoretical worst-case f d-divergences of global and local minimax samplers under the v-GLDP setting with uniform reference distribution H4 over finite space (k: 100).
We compare the worst-case f f-divergence under GDG for local and global minimax-optinne samplers across different values v E {0.1, 0.5, 1, 2.. The numerical results in Figures 7, 8, and demonstrate that for various sample sizes (10, 20, 100), the local minimax-optimal sampler consistently achieves lower minimax risk than the global sampler across all privacy parameter values.
E.6 Continuous sample space numerical results under GLDP
We follow the same experimental procedure described in Appendix E.4, with the only difference being that we now compare the local and global minimax-optimal samplers under v-GDP instead of e-L.P. The local and global universes, as well as the distribution generation process, remain unchanged. For the global minimax sampler, we use the construction provided in Corollary 3.8, while the local minimax sampler is instantiated from Theorem 4.1 with g Gy, We conduct the
48

---

comparison across various values of v 0.5, evaluating the resulting samplers using three f-divergences: KL divergence, total variation distance, and squared Hellinger distance.
KT.
TV
Sq. Hel
Warst Fdivergence
0.08
0.3
0.06
0.2
0.2
0.04
0.1
0.1
0.02
0.0
0.00
0.1
0.5
1.0
2.0
0.1
1.0
2.0
0.1
0.5
1.0
2.0
Global
Loral
Privacy parameter
Figure 10: Empirical worst-case f f-divergences of global and local minimax samplers under v-GLDP setting, over 100 experiments on a 1-D Laplace mixture.
As illustrated in Figure 10, in the v-GDP setting-similar to the s-LDP case-the local minimax sampler consistently achieves smaller worst-case f f-divergence than the global minimax sampler across all three divergences and privacy parameter values.
E.7 Additional numerical results on continuous sample space
We extend the experiment from Section 6.2 to the two-dimensional setting X R². Figure 11 compares the worst-case empirical f-divergence between the global sampler of Park et al. (17) and the local sampler described in Theorem 4.1 for g Ic-
We follow the same experimental procedure as Section 6.2, detailed in Appendix E.4, to generate 100 client distributions. Each distribution is constructed as mixture of 2-D Laplace components with fixed scale parameter = 1. The only difference from the one-dimensional case is the extension to 2-D Laplace mixtures.
The mixture class 2-D Laplace distributions with scale parameter is defined as
k A A(m,,)) b): [K] A 0,
[mm,l1 S $1 }
Pc =
Σ X = t=1
where C(m, b) denotes two-dimensional Laplace distribution with mean m IR.2 and scale To control the complexity of each mixture, impose upper bound K on the number of components per distribution.
Each distribution Py E Pe is generated by randomly sampling k, A,, and my follows: First, sample k Poisson(ko), and set = min(k + 1, K). Then, sample each m, I2² independently from the uniform distribution uniformly from the probability simplex P((k).. this experiment, following the setup in Park et al. [17], we use K 10 and Ko- 2.
the E ball {x R² ||ж|| s 1). and draw the weights (AI...., As)
The local and global universes are defined as Plocal P1/3,3, and P Pglobal Pi/9, be where he denotes the density of the two-dimensional Laplace distribution with mean zero and scale parameter b
In the two-dimensional case, similar to the one-dimensional setting, the local sampler outperforms the global sampler for nearly all fixed values of the privacy parameter.
Instructions for reproducing results
In this appendix, we provide instructions for reproducing the experiments and figures in the paper. For detailed description of the code, please refer to the provided file README. md. For tasks that require substantial runtime, we specify the running times. Tasks that complete in less than seconds excluded from such reporting.
49

---

KL
TV
Sq. Hel
0.08
Worst r-vvergeeenn
0.3
0.4
0.06
0.2
0.04
0.2
0.1
0.0
0.0
0.00
0.1
0.5
1.0
2.0
0.1
0.5
1.0
2.0
0.1
0.5
1.0
2.0
Privacy budget g
Figure 11: Empirical worst-case faaccassfffee f-divergences global and local minimax samplers under the pure LDP setting, over 100 experiments 2-D Laplace mixture.
All experiments were conducted on a system running Ubuntu 22.04.4 LTS, equipped with an Intel(R) Xeon(R) CPU @ 2.20GHz and 16GB of RAM.
E.1
Instructions for reproducing Figure
From the repository root, run python -m experiments. eep_ exp_LapWixture_van _visal to generate the output distributions, and then python -m plotting wat.splott__ae Looo__LpMixture_ee visual to produce Figure 1.
The measured running time in our environment for applying the minimax-optimal sampler to the original input distribution approximately 300 seconds.
F.2
Instructions for reproducing results for finite space
The finite space results are organized into six figures, grouped into two categories. Figures 3, 5, and present the worst-case divergences under pure LDP for different values {10,20 100). In contrast, Figures 7, 8, and 9 show the corresponding results under v-GLDP for the same values of k.
To generate Figures 3, 5, and 6, the script pooting/ploor httpp//ooootteet//eeeeeppeaaaeep peee_puurepp py with the -k argument to specify the desired value of For example, the following commands can be used to generate the respective plots:
python -m plotting. peecting-plot.... python python -m ltapinnggooooffite_eppeep --k 100
pure --k 20
wwt.tpooooottppppppeee_eeeeeeeep --k 10
To produce Figures 7, and run the script plotttig//llo.ffiiitte...D py with the corre- sponding k values:
python -m python -m wttpinngpoooo_fii___eeee_eeee --k 20 python -m
--k 10
--k
F.3 Instructions for reproducing results for continuous space
To reproduce Figure 4, first run the script experiments/ery http://pp.Daaaaaaaaixxpprrree py with differ- ent values of the privacy parameter The following commands correspond to E (0.1, 0.5, 1.0, 2.0). respectively:
python -m experiments.exp wwt.seeee....aaaalcciii.ppppppp --eps 0.1
--scale 1 --seed 1
python -m experiments exp..1DlaplaceMixxpurs eps 0.5
--scale 1
--seed 2
python -m experiments. exp exp_1DlaaplacoMix__pr eee 1.0 --scale 1 -- --seed 3
python experiments wtt.:eeeeppppppepeee. exp_11DaaplaceMMxx.purs --eps 2.0 --scale 1 --seed 4
These scripts can be executed independently and in any order, run in parallel. In our environment, running all four in parallel required approximately 600 seconds. After completion, run python -m plotting pltpppopiiiiaee 1DLaplaceMixxpprre to generate the final plots.
50

---

To reproduce Figure 10, execute the script pppprrimatts//xxx_llaaalaaaele ous values of the privacy parameter v. The following commands correspond to 0.1, 0.5, 1.0, and 2.0, respectively:
py with vari-
python -m apperriieetsseeepppp.aaaaaaooo.t
--uu 0.1 --scale 1 --seed
python -m http:/mmnts.epp__iiee exp_11LaaplaceMii_GGG. --nu 1.0 --scale 1 --seed
htt.://ss..eppp.baaaaaaaaei...oo --nu 0.5 --scale --seed
python -m experiments
python -m
wtt.p//mwss.eppp....aaaaaalllaaa --nu 2.0 --scale --seed
These scripts can be executed in any order or in parallel. In our environment, running all four in parallel required approximately 80 seconds. After completion, run python -m plotting pttssppot____1_ M.ot__1Daallaeeixx.co GLDP to generate the final figure.
To reproduce Figure I, run the script experiments/erp: htapatt//erppp.aaalaaaaiiiiiiit.
with different values of the privacy parameter The following commands correspond to (0.1,0.5, 2.0):
python experiments hwtp://mmw...eennmbbaaaaaaaaaaaa
-ps 0.1 --seed --dim 2
python -m experiments.exp.eeee.e.....s wttpssse......lppllaacee..pppppp --eps 0.5 --seed --dim 2
python -m experiments .ep_.allapplaacciii.ppuus --eps 1.0 --seed --dim 2
python -m
www..elaaplaaceiii.pppooo --eps 2.0 --seed --dim 2
These can be run independently or parallel. In our environment, running all four in par- allel required approximately 40 seconds. Once the first step is completed, python plotting plop_ploliiieeee plot_aalaapaaceiixpppuu --dim to generate the final figure.
G Broader impact
Our proposed optimal samplers designed under LDP guarantees and can be applied to privacy protection in generative modeling-a rapidly growing area of interest. A key obstacle to the adoption of privacy-preserving algorithms in practice the potential degradation model performance. By characterizing minimax-optimal samplers under two variants of LDP (functional and pure) and across two formulations (global and local), we develop samplers that minimize utility loss under given privacy budget. As result, our samplers help overcome this challenge and support broader real-world applicability.
Although an LDP sampler provides meaningful privacy guarantees, it cannot achieve perfect privacy without completely sacrificing there an inherent trade-off between the two. Moreover, Our samplers are designed for the single-sample setting, where each client releases only one privatized data point. Extending these guarantees scenarios involving multiple, potentially correlated releases is an important direction for future work (see Section 7). In practice, clients often contribute data through multiple channels, and aggregating these disclosures can lead greater privacy leakage.
51


Reviews:
[{"review_id": "AdBM57QJ0J", "reviewer": "Reviewer_sXTE", "summary": "This paper studies the problem of generating a sample from a\ndistribution under the constraints of local differential privacy.\nThis work extends previous work in two directions: 1) it studies\nsampling algorithms satisfying functional local differential privacy\nwith optimal global minimax risk 2) it studies local minimax risks of\nprivate samplers in the presence of public data. The proposed\nalgorithms are validate experimentally.", "questions": "Can you please provide a comparison between how you use public data an previous work [22] used them?\n\nIn the limitation you mentions the computational complexity of your samplers, can you give more details on it?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n- The paper presents two methods to identify private samplers that are\n  locally minimax optimal when a public distribution is available,\n\n- the paper characterizes samplers that are globally minimax optimal\n  and that satisfy functional LDP.\n\nWeaknesses\n\n- The focus of the paper on the local model makes the sampling problem\n  less about algorithms and more about finding the right parameters,\n\n- the paper doesn't give much intuition about the derived samplers.\n\nSeveral recent works have studied sampling from distributions under\nthe constraints of differential privacy in different models. This\npaper considers this problem in the local model of differential\nprivacy, where every user holds a distribution and aims at releasing a\nsample from it. More specifically, the paper focuses on minmax notions\nof utility of the samplers with respect to f-divergences. In\nparticular, the utility is defined at the user level rather than at\nthe protocol level as in works that have studied statistical tasks in\nthe local model. While certainly meaningful, this focus makes the\npaper more about figuring out the right setup and parameters of \nthe samplers rather than coming up with novel algorithm.  \nThe paper does this well focusing on problems that were not studied \nin previous works. The global minimax results extend the set of results available to\nfunctional LDP and to different discrete and continuous\nsamplers. Similarly to what I said above, functional DP was proposed\nin the context of the central model.  While it can certainly also be\nused for the local model, its properties and semantics are different\nand make some problem more interesting and some problem less\ninteresting. The results on local minimax extend previous work which\nstudied samplers with public data in the local model by providing\noptimal local minimax samplers. It is worth to notice that the paper\npresents two frameworks to do this. The experiments confirm the\ntheoretical results. Overall, I fund this paper contributing good\nresults to the theory of differentially private local samplers,\nalthough I didn't find them particularly exciting in terms of new\nideas required.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful and detailed review. We are glad they appreciated our contributions, including the extension to functional LDP and the characterization of optimal local minimax samplers. Below, we address each of the reviewer’s questions and concerns individually.\n\n&nbsp;\n>The focus of the paper on the local model makes the sampling problem less about algorithms and more about finding the right parameters.\n\nWhile global minimax private sampling under pure LDP has been studied previously (e.g., Park et al. [17]), our work extends this by developing both global and local minimax results under the more general functional LDP framework, which encompasses pure, approximate, and Gaussian LDP. This required introducing new assumptions, proof techniques, and a carefully defined local neighborhood that fundamentally differs from the global setting. These developments allow us to bridge global and local minimax frameworks and derive new linear and nonlinear samplers that are optimal in the local minimax sense under functional LDP. Importantly, we propose new algorithms tailored to this setting—not merely new parameters for existing ones. Our framework also lays a foundation for future work, including broader neighborhood definitions and scalable implementations, as outlined in the limitations.\n\n&nbsp;\n>The paper doesn't give much intuition about the derived samplers.\n\nWe thank the reviewer for their constructive feedback. While we made an effort to convey the intuition behind the derived samplers—through both textual explanations and visual illustrations—we agree that additional elaboration could help improve clarity. Below, we provide a complementary interpretation of the two main classes of samplers discussed in the paper: *linear* and *nonlinear* samplers.\n\nFor the linear samplers, such as the global sampler $\\mathbf{Q}^\\star_{c_1,c_2,h,g}$ defined by  $q^\\star_g(P)(x):=\\lambda^\\star_{c_1,c_2,g}p(x)+\\left(1-\\lambda^\\star_{c_1,c_2,g}\\right)h(x),$\nas presented in lines 204–206 of the manuscript, a natural interpretation is that the mechanism samples from the input distribution $P$ with probability $\\lambda^\\star_{c_1,c_2,g}$, and from the reference distribution $h$ otherwise. This probabilistic mixture reflects the privacy–utility trade-off: a larger $\\lambda^\\star_{c_1,c_2,g}$ yields outputs closer to $P$, while sampling from $h$ introduces the randomness required for privacy. This same intuition applies to all linear samplers derived in the paper.\n\nFor the nonlinear sampler presented in Theorem 5.1, the optimal sampling mechanism is given by  \n$$\\hspace{6cm}q(x)=\\text{clip}\\left(\\tfrac{1}{r_P}p(x);\\tfrac{\\gamma+1}{\\gamma+e^{\\varepsilon}}p_0(x), \\tfrac{(\\gamma+1)e^{\\varepsilon}}{\\gamma+e^{\\varepsilon}}p_0(x)\\right).$$\n\nAs described in lines 287–288 of the manuscript, this construction defines a nonlinear sampler by projecting the input distribution $P$ onto a family of distributions referred to as the *mollifier* $M_\\varepsilon$, as defined in the paper (see Figure 2).\nThe clipping operation ensures that the output distribution $\\mathbf{Q}^\\star_\\varepsilon(P)$ satisfies the LDP constraint while maintaining a close match to the original distribution $P$ in terms of $f$-divergence. In other words, $\\mathbf{Q}^\\star_\\varepsilon(P)$ belongs to the mollifier and is instance-optimal for the given input distribution. This approach yields a nonlinear transformation of $P$ that carefully balances privacy constraints and utility preservation.\n\nFigure 2 further illustrates the sampling process under the local minimax framework. It involves two steps: (1) if $P$ lies outside the local neighborhood of the public distribution $P_0$, it is projected inward; and (2) optimal sampling is performed using either a linear or nonlinear sampler, depending on the context.\n\nWe will incorporate these clarifications and interpretations in the final version to better communicate the intuition behind the derived samplers.\n\n&nbsp;\n>Can you please provide a comparison between how you use public data and previous work [22] used them?\n\nZamanlooy et al. [22] use public data as an explicit **optimization constraint** in their global minimax formulation, which is defined over discrete domains and restricted to linear samplers. Note that in this discrete domain, the sampling distribution can be expressed as $PK$, where $P$ is the data distribution (viewed as a vector) and $K$ is an LDP mechanism (viewed as a matrix that satisfies the LDP constraint). Zamanlooy et al. [22] considered $\\varepsilon$-LDP mechanisms $K$ that **preserve the public prior** $P_0$, enforcing $P_0K = P_0$.  This guarantees that the public data remains invariant under the mechanism while privacy is provided for private data. They then formulated their minimax optimization as:\n$$\\hspace{8cm}\\inf_{\\\\substack{K \\in\\mathcal{Q_\\varepsilon}\\\\\\\\P_0K=P_0}}\\sup_{P \\in\\mathcal{P}(\\mathcal{X})}D_f(P\\\\|PK).$$\n\nIn contrast, we use public data in a conceptually different way. Instead of treating it as a hard constraint, we use the public distribution $P_0$ to define a **local neighborhood** $N_\\gamma(P_0)$. The worst-case input distributions are then considered within this neighborhood. This leads to a **local minimax formulation** of the private sampling problem over a general sample space, without restricting to linear mechanisms. Specifically, we search over mechanisms $\\mathbf{Q}\\in\\mathcal{Q_\\varepsilon}$, where $\\mathcal{Q_\\varepsilon}$ again denotes the class of $\\varepsilon$-LDP samplers:\n\n$$\\hspace{8cm}\n\\inf_{\\mathbf{Q}\\in\\mathcal{Q_\\varepsilon}}\\sup_{P \\in N_\\gamma(P_0)}D_f\\big(P\\\\|\\mathbf{Q}(P)\\big).\n$$\n\nNote that the formulation of [22] is a special form of our setting: $\\mathbf{Q}(P)=PK$ where $K$ is an $\\varepsilon$-LDP sampler. Our goal is to move beyond the overly pessimistic global worst-case risk and instead focus on distributions that are close to $P_0$, which is assumed to be publicly available to all users. This enables a more refined and robust characterization of optimal samplers from a local minimax perspective. It is important to note that in the formulation of Zamanlooy et al., having public data does **NOT** necessarily lead to a more accurate sampling (smaller minimax risk), whereas this is the case in our formulation.\n\nThat said, as shown in Theorems 4.1 and 5.1, the local minimax-optimal samplers $Q^\\star_{g, N_\\gamma(P_0)}$ and $Q^\\star_{\\varepsilon,N_\\gamma(P_0)}$ both satisfy $Q^\\star_{g, N_\\gamma(P_0)}(P_0)=P_0$ and $Q^\\star_{\\varepsilon, N_\\gamma(P_0)}(P_0)=P_0$, even though the preservation of $P_0$ is not explicitly enforced as a constraint. \nThis demonstrates that our formulation inherently respects the public data when the input distribution coincides with it, without requiring this condition to be imposed as part of the optimization, meaning that our formulation is a non-trivial generalization of Zamanlooy et al. [22] to general data distribution (not necessarily to discrete distribuition, as in [22]).\n\n&nbsp;\n>In the limitation you mentions the computational complexity of your samplers, can you give more details on it?\n\nWe thank the reviewer for raising this important point regarding computational complexity.\nOverall, the samplers derived in this work fall into two categories: (1) *inear samplers*, such as the core sampler in Theorem 4.1, and (2) *nonlinear samplers* involving clipping functions, as in Theorem 5.1.\n\nThe linear sampler $\\\\mathbf{Q}^\\\\star_{c_1,c_2,h,g}$ defined in Theorem 3.4 (Equation (4)), has density $q^\\\\star_g(P)(x):=\\\\lambda_{c_1,c_2,g}^{\\\\star}\\\\,p(x)+\\\\left(1-\\lambda_{c_1,c_2,g}^{\\star} \\right) h(x)$,\na convex combination of the input $p$ and reference $h$. Its complexity lies in computing the mixing coefficient $\\lambda_{c_1,c_2,g}^{\\star}$, which is given by $\\lambda_{c_1,c_2,g}^{\\star} = \\inf_{\\beta\\geq0}\\frac{e^{\\beta}+\\frac{c_2-c_1}{1-c_1}\\left(1+g^*(-e^{\\beta})\\right)-1}{(1-c_1)e^{\\beta}+c_2-1}$. \n\nIn many cases—e.g., pure, approximate, and Gaussian LDP—the conjugate $g^*$ is known in closed form, allowing this optimization to be solved analytically or efficiently numerically. Thus, the linear sampler is computationally tractable.\n\nIn contrast, the nonlinear sampler in Theorem 5.1 is defined by the mapping $ \\mathbf{Q}^\\star_\\varepsilon(P)$, whose density is\n$$\\hspace{6cm}q(x)=\\text{clip}\\left(\\tfrac{1}{r_P}p(x);\\tfrac{\\gamma+1}{\\gamma+e^{\\varepsilon}}p_0(x), \\tfrac{(\\gamma+1)e^{\\varepsilon}}{\\gamma+e^{\\varepsilon}}p_0(x)\\right),$$\nwhere the constant $r_P>0$ is selected so that $\\int_{\\mathbb{R}^n}q(x)dx=1$. The main computational burden lies in determining this normalizing constant $r_P$. To compute it, we define the parametric family\n$q_r(x):=\\text{clip}\\left( \\tfrac{1}{r}p(x); \\tfrac{\\gamma+1}{\\gamma+e^{\\varepsilon}}p_0(x),\\tfrac{(\\gamma+1)e^{\\varepsilon}}{\\gamma+e^{\\varepsilon}}p_0(x) \\right)$, and search for a value $r>0$ such that $\\int_{\\mathbb{R}^n}q_r(x)dx=1$. It can be shown that the endpoints $r_1:=\\tfrac{\\gamma+e^{\\varepsilon}}{\\gamma(\\gamma+1)}$ and $r_2:=\\tfrac{\\gamma(\\gamma+e^{\\varepsilon})}{e^{\\varepsilon}(\\gamma+1)}$ satisfy $\\int q_{r_1}\\ge1$ and $\\int q_{r_2} \\le 1$, and that $r \\mapsto \\int q_r(x)dx$ is continuous. Therefore, $r_P$ can be found using the bisection method on the interval $(r_1,r_2)$.\n\nWhile the bisection method requires only a logarithmic number of steps, the main computational cost lies in evaluating the integral $I(r)=\\int_{\\mathbb{R}^n}q_r(x)dx$ at each step. This is tractable in low-dimensional settings but quickly becomes prohibitive as dimensionality increases.\n\nA promising direction to mitigate this is to bypass explicit integration by designing approximate samplers $\\mathbf{Q}$ that minimize the divergence  $D_f(\\mathbf{Q}\\\\|\\mathbf{Q}^\\star_\\varepsilon(P))$, where $\\mathbf{Q}^\\star_\\varepsilon$ is the optimal $\\varepsilon$-LDP sampler. This offers a rich path for future work, especially in scaling optimal mechanisms to high-dimensional domains."}, {"review_id": "CYb6TKoBSP", "reviewer": "Reviewer_BPVM", "summary": "This paper investigates the problem of distribution sampling under local differential privacy (LDP). The authors begin by examining the global setting, where they extend existing results to both approximate LDP and functional LDP. They then shift focus to the local setting, in which the distribution class is restricted to a neighborhood around a fixed distribution $P_0$. Building on their global sampling approach, they develop a sampler that achieves the optimal minimax rate in the local setting.", "questions": "The questions are included in the \"Strengths And Weaknesses\" section.", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\nThe paper addresses an important and timely problem in distribution sampling under local differential privacy, and it proposes a solution that achieves the optimal minimax rate. The extension from the global to the local setting is meaningful and adds significant value to the literature.\n\nWeaknesses and Questions:\n\n1. The presentation could be improved, particularly regarding the purpose and organization of Section 3. Although the paper primarily focuses on local sampling, Section 3 is entirely devoted to global sampling. While I understand parts of section 3 is necessary for later sections like extension to functional LDP case and introducing $Q^*_g$, it would be clearer to restructure this material into a dedicated subsection.\n2. The proposed sampler in Theorem 4.1 is not computation efficient for general $\\widetilde{\\mathcal{P}}$. In particular, the projection step to compute $\\hat{P}$ can be computation demanding. By the way, what's the meaning of \"minimizes $\\inf_{P'\\in N(P_0)} D_f(P||P')$\"? For any fixed $P$ and $P_0$, this infimum is a constant value.\n3. The relationship between global and local sampling is not fully clarified. Intuitively. one would assume that since local sampler is restricted to a smaller distribution set, it will achieve a better minimax rate. However, this improvement is not quantified in the paper. If general case is infeasible to quantify, is it possible to at least give concrete examples to demonstrate the rate gap between global and local sampling.\n\nThere are some other minor comments:\n1. what is the definition of $g^*$ in equation 4?\n2. The definition of $\\widetilde{P}$ is unclear in section 4, are we still considering class defined in equation (2) or a general distribution class is considered?", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful feedback and for pointing out areas needing clarification, such as the definitions of $g^*$ and $\\tilde{\\mathcal{P}}$. We are also glad they found the extension from global to local minimax meaningful and acknowledged our contribution to private distribution sampling. Below, we address each of the reviewer’s questions and comments individually.\n\n&nbsp;\n\n**1. Presentation and Organization of Section 3:**\n\nWe appreciate the reviewer’s suggestion regarding the presentation and structure of Section 3. While the main focus of the paper is on local sampling, we included Section 3 to provide the necessary theoretical groundwork for the subsequent sections, including the extension to functional LDP, the formulation of key assumptions, and the definition of global samplers used in the analysis. Specifically, we study global minimax samplers under the general framework of functional LDP and derive compact characterizations of the optimal samplers. As noted at the beginning of Section 3 (lines 170–171), these global samplers serve as proxies for constructing local minimax-optimal samplers in the following sections.\n\nWe aimed to preserve a natural progression in the paper’s structure, moving from functional LDP global minimax in Section 3, to functional LDP local minimax in Section 4, and then to pure LDP local minimax in Section 5. This order reflects the way the results were derived, with each step building on the previous one. That said, we agree that the purpose of Section 3 could be emphasized more clearly. In the revision, we will improve the framing of this section and better articulate its connection to the rest of the paper. We will also consider reorganizing key parts into a dedicated subsection to enhance clarity and flow.\n\n&nbsp;\n\n**2. Computational Efficiency of the Proposed Sampler and Clarification of the Projection Step in Theorem 4.1:**\n\nFor general $ f $-divergences and sample spaces $\\mathcal{X}$, this projection step may require solving a constrained optimization problem, and its complexity is on the same order as that of the clipping-based projection described in Theorem 5.1.\n However, as shown by Husain et al. [7], in certain special cases such as when the $f$-divergence is the KL divergence and the sample space is finite, the projection problem admits a closed-form solution using the Karush-Kuhn-Tucker (KKT) conditions. In these settings, the projection step can be carried out efficiently without incurring additional computational overhead. \n\nAs the reviewer points out, the projection can be computationally demanding, particularly in high-dimensional settings, even though a closed-form expression for it is available. This is because the expression involves a clipping step that depends on a normalization constant (similar to $r_P$ in the statement of Theorem 5.1). Computing this constant requires performing numerical integration over a high-dimensional space, which can be costly and often becomes the main computational bottleneck.\n\nIn the following, we include a discussion on the computational complexity of the samplers proposed in our work. Overall, the samplers derived in this work fall into two categories: (1) *linear samplers*, such as the core sampler in Theorem 4.1, and (2) *nonlinear samplers* involving clipping functions, as in Theorem 5.1.\n\nThe linear sampler $\\mathbf{Q}\\_{c_1,c_2,h,g}^\\star$, defined in Theorem 3.4 (Equation (4)), has density $q_g^{\\star}(P)(x) := \\lambda_{c_1, c_2, g}^{\\star} p(x) + \\left(1 - \\lambda_{c_1, c_2, g}^{\\star} \\right) h(x)$,\na convex combination of the input $p$ and reference $h$. Its complexity lies in computing the mixing coefficient\n$\\lambda_{c_1,c_2,g}^{\\star} = \\inf_{\\beta\\geq0}\\frac{e^{\\beta}+\\frac{c_2-c_1}{1-c_1}\\left(1+g^*(-e^{\\beta})\\right)-1}{(1-c_1)e^{\\beta}+c_2-1}$.\n\nIn many cases—e.g., pure, approximate, and Gaussian LDP—the conjugate $g^*$ is known in closed form, allowing this optimization to be solved analytically or efficiently numerically. Thus, the linear sampler is computationally tractable.\n\nIn contrast, the nonlinear sampler in Theorem 5.1 is defined by the mapping $\\mathbf{Q}^\\star_\\varepsilon(P) $, whose density is\n$$\\hspace{6cm}\nq(x) = \\operatorname{clip}\\left( \\tfrac{1}{r_P}p(x); \\tfrac{\\gamma+1}{\\gamma+e^{\\varepsilon}}p_0(x), \\tfrac{(\\gamma+1)e^{\\varepsilon}}{\\gamma+e^{\\varepsilon}}p_0(x) \\right),\n$$\nwhere the constant $r_P>0 $ is selected to ensure normalization condition $\\int_{\\mathbb{R}^n} q(x) dx = 1 $. The main computational burden lies in determining this normalizing constant $ r_P $. To compute it, we define the parametric family\n$q_r(x) := \\operatorname{clip}\\left( \\tfrac{1}{r}p(x); \\tfrac{\\gamma+1}{\\gamma+e^{\\varepsilon}}p_0(x), \\tfrac{(\\gamma+1)e^{\\varepsilon}}{\\gamma+e^{\\varepsilon}}p_0(x)\\right)$,\nand search for a value $ r > 0 $ such that $ \\int_{\\mathbb{R}^n} q_r(x) dx = 1 $. It can be shown that the endpoints\n$r_1 := \\tfrac{\\gamma+e^{\\varepsilon}}{\\gamma(\\gamma+1)}$ and $r_2 :=\\tfrac{\\gamma(\\gamma+e^{\\varepsilon})}{e^{\\varepsilon}(\\gamma+1)}$\nsatisfy $ \\int q_{r_1}\\ge 1 $ and $ \\int q_{r_2} \\le 1 $, and that $ r \\mapsto \\int q_r(x)\\,dx$ is continuous. Therefore, $r_P$ can be found using the bisection method on the interval $ (r_1,r_2)$.\n\nWhile the bisection method requires only a logarithmic number of steps, the main computational cost lies in evaluating the integral $I(r) = \\int_{\\mathbb{R}^n} q_r(x)  dx$ at each step. This is tractable in low-dimensional settings but quickly becomes prohibitive as dimensionality increases.\n\nRegarding the reviewer’s question about the expression “$\\hat{P}$ minimizes $\\inf_{P' \\in N(P_0)} D_f(P \\\\| P')$,” we intended to convey that we find the distribution $\\hat{P}$ that minimizes $D_f(P \\\\| P')$ over all $P' \\in N(P_0)$. The reviewer is correct, and we will revise the text accordingly for clarity.\n\n&nbsp;\n\n**3. Relationship Between Global and Local Sampling and the Associated Rate Gap:**\n\nUnder an $\\varepsilon$-LDP constraint, consider the global model class\n$$\\hspace{5cm}\\tilde{\\mathcal{P}}\\_{c_1,c_2,\\mu} = \\\\{P \\in \\mathcal{P}(\\mathcal{X}): \\\\; P \\ll \\mu \\\\;  , \\quad c_1 \\le \\frac{dP}{d\\mu} \\le c_2\n    \\quad \\mu\\text{-a.e.}\\\\}.$$\nThe global minimax risk for this class is given in Equation (6), line 227:\n$$\\hspace{5cm}\\mathcal{R}\\bigl(Q_{\\mathcal{X},\\\\,\\tilde{\\mathcal{P}},g_{\\varepsilon}},\n                 \\tilde{\\mathcal{P}},f\\bigr)= \\frac{1-r_1}{r_2 - r_1}\\\\,f(r_2)+\\frac{r_2 - 1}{r_2 - r_1}\\\\,f(r_1),$$\nwhere $r_1 = c_1 \\cdot \\frac{(1 - c_1)e^{\\varepsilon} + c_2 - 1}{c_2 - c_1}$ and\n$r_2 = \\frac{c_2}{c_2 - c_1} \\cdot \\frac{(1 - c_1)e^{\\varepsilon} + c_2 - 1}{e^{\\varepsilon}}.\n$\n\nThe local minimax risk is defined over the neighbourhood\n$N_{\\gamma}(P_0) :=\\\\{\n    P \\in \\mathcal{P}(\\mathcal{X}):\n    E_{\\gamma}(P \\\\| P_0) = E_{\\gamma}(P_0 \\\\| P) = 0\n\\\\},\n$\nwhich satisfies $N_{\\gamma}(P_0) \\subseteq \\tilde{\\mathcal{P}}\\_{c_1,c_2,\\mu}$.\nAs defined in line 1249 of the technical appendix, the corresponding local minimax risk is\n$$\\hspace{5cm}\\mathcal{R}\\bigl(\n      Q_{\\mathcal{X},N_{\\gamma}(P_0),\\varepsilon},\n      N_{\\gamma}(P_0),f\n\\bigr)\n  =\n   \\frac{1 - r_1}{r_2 - r_1}f(r_2)\n   +\n   \\frac{r_2 - 1}{r_2 - r_1}f(r_1),\n$$\nwhere $\nr_1 = \\frac{e^{\\varepsilon} + \\gamma}{\\gamma(\\gamma + 1)}$ and\n$r_2 = \\frac{\\gamma(e^{\\varepsilon} + \\gamma)}{e^{\\varepsilon}(\\gamma + 1)}.\n$\n\nWhile the difference between the local and global risks can be computed in closed form via direct subtraction, the resulting expression is not particularly insightful, as it depends on several problem-specific parameters, including $ (c_1, c_2, \\gamma) $, the sample space, and the privacy level $ \\varepsilon $. Although the subtraction can be evaluated for any given instance, it does not, in general, yield a simple or interpretable expression.\n\nTo better illustrate the improvement, we provide numerical comparisons in both discrete and continuous settings. In the discrete case (Figures 3, 5, 6), we compare the global and local minimax-optimal samplers for $\\mathcal{X} = [k]$, where the global class is\n$\\tilde{\\mathcal{P}}\\_{\\text{global}} = \\mathcal{P}([k]) = \\tilde{\\mathcal{P}}\\_{0,k,\\mu_k},$\nwith $\\mu_k$ being the uniform distribution. The local neighbourhood is defined as\n$\\tilde{\\mathcal{P}}\\_{\\text{local}} = \\mathcal{N}\\_\\gamma(\\mu_k) = \\tilde{\\mathcal{P}}\\_{\\frac{1}{\\gamma}, \\gamma, \\mu_k},$\nwith $\\gamma = \\frac{k}{2} - 1$, ensuring that $\\mathcal{N}_\\gamma(\\mu_k) \\subseteq \\mathcal{P}([k])$.\n\nWe instantiate both the global and local neighbourhoods using the parameters defined in Section 6.1, and compute the exact minimax risks in each case. Figures 3, 5, and 6 present these theoretical worst-case risks, clearly demonstrating the benefit of tailoring the mechanism to the local neighbourhood.\nThese plots consistently illustrate a significantly improved minimax rate in the local setting compared to the global one, across various $f$-divergences and parameter ranges.\n\n\n&nbsp;\n\n**4. Definition of $ \\boldsymbol{g^*} $ in Equation (4):**\n\nWe define $g^{\\*}$ to be the convex conjugate of the function $g$, as introduced in the notation section. Formally, it is given by\n$g^{*}(y) = \\sup_{x \\in \\text{dom}(g)} \\Bigl( xy - g(x) \\Bigr)$.\nTo improve clarity and completeness, we will include this formal definition in the notation section.\n\n&nbsp;\n\n**5. Definition of $ \\boldsymbol{\\tilde{\\mathcal{P}}} $ in Section 4:**\n\nAs for the definition of $ \\tilde{\\mathcal{P}} $ in Section 4, we clarify that $ \\tilde{\\mathcal{P}} $ refers to a general set of possible distributions relevant to the problem under consideration. In particular, in Section 4, $ \\tilde{\\mathcal{P}} $ may represent any general class of continuous distributions, subject only to the constraint\n$\nN_\\gamma(P_0) \\subseteq \\tilde{\\mathcal{P}},\n$\nwhich is assumed in the statement of Theorem 4.1. We will include a note at the beginning of the section to make this generality of $ \\tilde{\\mathcal{P}} $ explicit."}, {"review_id": "GiYZPT7vYY", "reviewer": "Reviewer_aNM6", "summary": "In this paper, the authors generalize the optimal minimax LDP sampling procedure of Park to the functional-LDP setting.\nThen, they consider distributions that are neighbors of a fixed distribution $P_0$ and present 2 algorithms to perform sampling in the pure LDP setting. Lastly, authors compare their 2 algorithms with synthetic experiments.", "questions": "Could you discuss the choice of distribution class ?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- The paper is well written, the hypotheses are appropriately discussed, and the results statements are clear.\n- The generalization of the work of Park to the functional LDP setting is an interesting and new contribution\n- The existence of a minimax optimal sampler that is point-wise better than the one derived from the generalization of the work of Park is also an interesting contribution.  \n\nWeaknesses\n- The class of distributions for which the sampler is optimal is restricted (the density verifies: c1 h(x) <= p(x) <= c2 h(x)). Although some restrictions are necessary to exclude trivial samplers, it is unclear to me why this particular condition arises or whether other choices could have been made.", "was_revised": true, "final_justification": "I have no more questions. I keep my score.", "rebuttal": "We thank the reviewer for their thoughtful review and insightful question. We are glad that they found the paper well written and appreciated our contributions, including the generalization of the global minimax framework and the introduction of instance-optimal samplers. Below, we provide a detailed discussion of the distribution class used in our work.\n\n> The class of distributions for which the sampler is optimal is restricted (the density verifies: $c_1 h(x) \\leq  p(x) \\leq c_2 h(x)$). Although some restrictions are necessary to exclude trivial samplers, it is unclear to me why this particular condition arises or whether other choices could have been made. \n\n> Could you discuss the choice of distribution class?\n\nWe thank the reviewer for raising this important point. The condition $c_1 h(x) \\leq p(x) \\leq c_2 h(x)$ used to define the distribution class $\\tilde{\\mathcal{P}}_{c_1, c_2, h}$ may seem restrictive at first glance, but it arises naturally from the need to balance generality with analytical tractability in LDP sampling.\n\nAs discussed in Park et al. [17], one may consider broader classes such as: (i) $\\mathcal{P}(\\mathbb{R}^n)$, the set of all probability measures on $\\mathbb{R}^n,$ or (ii) $\\mathcal{C}(\\mathbb{R}^n)$, the set of all continuous distributions on $\\mathbb{R}^n$. However, for such general choices, it has been shown that the minimax rate is vacuous, that is, any $\\varepsilon$-LDP sampling mechanism attains the largest possible value of $f$-divergence in the worst case (see Proposition 3.2 in Park et al.). As a result, all mechanisms perform equally poorly under these settings, making meaningful comparison or claims of optimality infeasible.\n\nTo obtain nontrivial and practically useful bounds, one must restrict attention to more regular classes of distributions. The class $ \\tilde{\\mathcal{P}}_{c_1, c_2, h} $, which consists of distributions whose densities (with respect to a general base measure such as Lebesgue) are bounded between two scalings of a reference function $ h $, is one such choice. This class offers two key properties: (i) it includes a wide range of realistic distribution families (so it is rich enough), as we illustrate below, and (ii) it ensures that the worst-case $ f $-divergence is non-vacuous.\n\nThis modeling choice is not purely theoretical. As shown in Example 3.1 of our manuscript, *mixtures of Gaussian or Laplace distributions* with bounded location parameters fall within this class. For instance, Laplace mixtures supported within the $\\ell_1$ unit ball satisfy $\\\\tilde{\\mathcal{P}}_{\\\\mathcal{L}} \\\\subseteq \\\\tilde{\\\\mathcal{P}}\\_{e^{-1/b}, e^{1/b}, h\\_{\\\\mathcal{L}}}$\nand Gaussian mixtures with bounded means lie in $ \\\\tilde{\\\\mathcal{P}}\\_N \\subseteq \\\\tilde{\\\\mathcal{P}}\\_{0, 1, h\\_{\\\\mathcal{N}}},$\nfor suitable choices of the reference functions $h\\_{\\\\mathcal{L}} $ and $h\\_{\\\\mathcal{N}} $ as defined in Example 3.1. These examples demonstrate that the proposed model captures a broad and practically relevant class of distributions.\n\nIn summary, while other distribution classes are conceivable, the choice of $\\tilde{\\mathcal{P}}_{c_1, c_2, h}$ provides a balanced trade-off between expressiveness and analytical feasibility, and encompasses many distribution families relevant to real-world applications."}, {"review_id": "xrTG1ubSPy", "reviewer": "Reviewer_xp8W", "summary": "This paper studies how to generate private samples from a user’s data under local differential privacy (LDP).  In particular, the authors show that the locally minimax-optimal private sampler can be derived from the global solution restricted to a local neighborhood. They provide explicit formulas for these samplers and prove they are optimal for a broad class of privacy definitions. Experiments on both discrete and continuous data show that the proposed local samplers outperform existing global methods in terms of accuracy across various privacy levels.", "questions": "Please see the Weaknesses.", "limitations": "Please see the Weaknesses.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\nThe paper is well-organized and logically structured, with a clear progression from global to local minimax analysis. This work makes a contribution to the field of private sampling by introducing a local minimax-optimal framework that extends beyond traditional worst-case analysis.\n\nWeaknesses:\n\n1. The condition $\\frac{c_2 - c_1}{1 - c_1} \\in \\mathbb{N}$ in Assumption 3.2 is somewhat restrictive and lacks clear justification, potentially limiting the generality of the results. What is the practical impact of requiring $\\\\frac{c_2 - c_1}{1 - c_1} \\in \\mathbb{N}$? Can you demonstrate that this condition approximately holds for common distributions or suggest a relaxation?\n2. The intuition behind the superiority of the non-linear sampler, currently deferred to the appendix, would be more impactful if summarized earlier in the main manuscript to guide the reader’s understanding.\n3. The practical utility of the proposed method remains unclear due to the lack of experiments on real-world datasets. Including a discussion on potential applications, such as private estimation or generative modeling, would help contextualize the broader impact. \n4. While the neighborhood-based formulation builds on prior work, the connection to existing literature in local differential privacy estimation is not sufficiently emphasized. \n5. In high-dimensional settings, does the clipping technique outlined in Theorem 5.1 become computationally prohibitive? It would be helpful to discuss the associated complexity and whether efficient approximations or relaxations are feasible.\n6. The relationship between the proposed local minimax framework and instance-optimal differential privacy (e.g., Feldman et al. [44]) is not explicitly addressed. Clarifying this connection could provide further insight, particularly regarding implications for private SGD or generative modeling.", "was_revised": true, "final_justification": "Most of my issues have been addressed.", "rebuttal": "We thank the reviewer for their constructive feedback. We are glad they found the paper well-organized and appreciated our contribution to private sampling via a local minimax-optimal framework that extends beyond worst-case analysis. Below, we address each of the reviewer’s comments in detail.\n\n&nbsp;\n\n**1. The Condition $\\\\boldsymbol{\\frac{c_2 - c_1}{1 - c_1} \\in \\mathbb{N}}$:**\n\nWe define $\\tilde{\\mathcal{P}}$ as the set of distributions of interest over a sample space $\\mathcal{X}$. To enable a unified theoretical treatment of both discrete and continuous settings, we restrict  $\\tilde{\\mathcal{P}}$ to be $\\tilde{\\mathcal{P}}_{c_1,c_2,\\mu}:=\\\\{P\\in\\mathcal{P}(\\mathcal{X}): P \\ll \\mu,\\\\; c_1\\leq\\frac{dP}{d\\mu}\\leq c_2\\\\; \\mu\\text{-a.e.}\\\\}$ for some measure $\\mu$. As shown in Park et al. [17] and mentioned in the manuscript, such restriction is necessary to avoid the trivial result. For this general setting, we assume the technical condition $\\frac{c_2-c_1}{1-c_1} \\in \\mathbb{N}$ to facilitate the construction of our proofs via a decomposability argument. \n\nIn the discrete case, where the domain is $[k]$, we define $\\mathcal{P}([k])=\\tilde{\\mathcal{P}}_{0,k,\\mu_k}$, where $\\mu_k$ is the uniform distribution over $[k]$. In this setting, we have $\\mathcal{X}=[k]$, $c_1=0$, $c_2=k$, and $\\mu=\\mu_k$, which yields $\\frac{c_2-c_1}{1-c_1}=k \\in\\mathbb{N}$. Thus, the above assumption trivially holds.\n\nIn the continuous case, following the approach of Park et al. [17], we assume $\\tilde{\\mathcal{P}} \\subset  \\tilde{\\mathcal{P}}\\_{c_1,c_2,\\mu}$ with base measure $\\mu$ being Lebesgue.  Here, $\\tilde{\\mathcal{P}}_{c_1, c_2, \\mu}$ acts as a tractable superset of the true distribution class. If $\\frac{c_2-c_1}{1-c_1}\\notin\\mathbb{N}$ for the original parameters, one can slightly increase $c_2$ or decrease $c_1$ to satisfy the condition. This adjustment results in a slightly enlarged superset, which is still consistent with the modeling assumption that $\\tilde{\\mathcal{P}}$ lies within a known, manageable class of distributions.\n\nFor example, setting $c_1=0$ always ensures the condition holds for any integer $c_2$. Moreover, in some natural families of distributions—such as mixtures of Gaussians with shared variance (see Example 3.1)—the assumption is satisfied without needing any relaxation.\n\nIn summary, the condition $\\frac{c_2-c_1}{1-c_1}\\in\\mathbb{N}$ is not restrictive: it is either automatically satisfied in discrete settings, or can be enforced without loss of generality in continuous ones, purely to streamline the technical development of the theory.\n\n&nbsp;\n\n**2. Intuition Behind the Outperformance of the Non-Linear Sampler:**\n\nWe thank the reviewer for the insightful suggestion. The non-linear sampler outperforms the linear one because it is not only worst-case optimal but also instance-optimal: for each input distribution $P \\in \\tilde{\\mathcal{P}}_{c_1,c_2,\\mu}$ and any $f$-divergence $D_f$, it minimizes $D_f(P\\\\|\\mathbf{Q})$ over all admissible $\\mathbf{Q}$ satisfying $\\varepsilon$-LDP (see Proposition D.2, line 1273). This instance-optimality arises because the non-linear sampler is constructed by solving the optimization problem for each individual $P$, producing a privatized distribution that minimizes the divergence from $P$ under the given LDP constraints. In contrast, the linear sampler applies the same transformation across all inputs. To provide clearer context for the reader, we will incorporate this intuition before presenting the comparison between the linear and non-linear samplers in the main manuscript.\n\n&nbsp;\n\n**3. Practical Utility of the Proposed Samplers and Discussion of Potential Applications:**\n\nWe thank the reviewer for the suggestion. We agree that including concrete downstream applications helps underscore the potential impact of our framework.\n\nOur framework is particularly relevant in settings where private samples must be generated in the presence of public data. For example, recent work on differentially private next-token prediction (e.g., Flemings et al. [28]) forms sampling distributions by linearly combining private and public distributions (e.g., from a public LLM), closely resembling our linear samplers. Our approach offers a principled, theoretically grounded alternative with formal optimality guarantees.\n\nAs discussed in the introduction, our work is also motivated by the growing relevance of personalized collaborative learning [18–20], where individual models are trained collaboratively and public data may reflect privatized information shared by other users. Since real-world distributions are rarely worst-case, our local minimax formulation provides a more realistic and effective framework for capturing achievable performance in practice. This makes our approach applicable to tasks such as private model fine-tuning, federated estimation, and privacy-preserving generative modeling.\n\nWe acknowledge that our experiments are limited to synthetic data due to the computational overhead of the clipping step in high-dimensional settings, as noted in the limitations section (lines 328–333). A promising direction for future work is to develop a scalable approximation for the optimal sampler that does not require clipping. Such approximation would enable us to implement private sampling on high-dimensional real datasets.\n\n&nbsp;\n\n**4. Connection to Existing Literature in LDP Estimation:**\n\nWe thank the reviewer for pointing this out. Several prior works have explored local minimax formulations under DP, primarily in estimation settings. For example, Chen et al. [45] study discrete distribution estimation under local DP using neighborhoods around a reference distribution. McMillan et al. [47] and Duchi et al. [43] develop locally minimax estimators for 1D parameters in the central and local models, respectively. Asi et al. [48] extend this to function estimation, and Feldman et al. [44] study nonparametric density estimation with both local and instance-optimal guarantees.\n\nThus, local minimax formulations using neighborhood structures have been well-studied in DP estimation and distribution learning, with definitions tailored to specific inference goals. As outlined in the related work section, while our focus differs in that we study private sampling rather than estimation, our formulation adopts a similar neighborhood-based perspective, adapted to the sampling setting. We will revise the related work section to clarify this connection and include relevant context.\n\n&nbsp;\n\n**5. Computational Complexity of Clipping in High Dimensions:**\n\nThe optimal sampler in Theorem 5.1 is defined by the mapping $\\mathbf{Q}^\\star_\\varepsilon(P)$, whose density is  \n$$\n\\hspace{6cm}q(x)=\\text{clip}\\big(\\tfrac{1}{r_P}p(x);\\tfrac{\\gamma+1}{\\gamma+e^{\\varepsilon}}p_0(x),\\tfrac{(\\gamma+1)e^{\\varepsilon}}{\\gamma+e^{\\varepsilon}}p_0(x)\\big),\n$$\nwhere $r_P>0$ is chosen so that $\\int_{\\mathbb{R}^n}q(x)dx=1$. Therefore, the computational burden of $\\mathbf{Q}^\\star_\\varepsilon(P)$ is dominated by computing $r_P$.\nTo that end, consider the family $q_r(x):=\\text{clip}\\bigl(\\tfrac{1}{r}p(x);\\tfrac{\\gamma+1}{\\gamma+e^{\\varepsilon}}p_0(x),\\tfrac{(\\gamma+1)e^{\\varepsilon}}{\\gamma+e^{\\varepsilon}}p_0(x)\\bigr)$ and search for $r>0$ satisfying $\\int_{\\mathbb{R}^n}q_r(x)dx=1$. Let $r_1:=\\tfrac{\\gamma+e^{\\varepsilon}}{\\gamma(\\gamma+1)}$ and $r_2:=\\tfrac{\\gamma(\\gamma+e^{\\varepsilon})}{e^{\\varepsilon}(\\gamma+1)}$. It can be shown that $\\int_{\\mathbb{R}^n}q_{r_1}(x)dx\\ge1$ and $\\int_{\\mathbb{R}^n}q_{r_2}(x)dx\\le1$, while the map $r\\mapsto\\int q_r(x)dx$ is continuous. Therefore, the desired normalizing constant $r_P$ can be computed via the bisection method with initial endpoints $(r_1,r_2)$.\n\nWhile the bisection procedure is efficient, the repeated numerical integration required at each step can become computationally prohibitive in high-dimensional settings. This underscores the need for alternative approaches that avoid explicit integration. One promising direction is to design approximate samplers by minimizing $D_f(\\mathbf{Q}\\\\|\\mathbf{Q}^\\star_\\varepsilon(P))$, where $\\mathbf{Q}^\\star_\\varepsilon$ is the optimal $\\varepsilon$-LDP sampler.\n\nWe consider these directions to be promising avenues for future work, as they address an important and nontrivial challenge in scaling optimal clipping-based mechanisms to high-dimensional domains.\n\n&nbsp;\n\n**6. Connection to Instance-Optimal Differential Privacy:**\n\nThe concept of instance-optimality, formulated by Feldman et al. [44], refers to algorithms that perform nearly as well on a given instance as the best differentially private algorithm designed specifically for that instance and its neighborhood. To avoid trivial solutions, performance is benchmarked not just against the instance itself but over a surrounding neighborhood, ensuring meaningful generalization without requiring the algorithm to be tailored to each instance.\n\n Instane-optimality captures the idea that algorithms should adapt to the \"hardness\" of the input rather than the worst case—particularly useful when there is a large gap between typical and worst-case performance, as in nonparametric estimation.\n\nIn contrast, our *local minimax* approach evaluates worst-case risk over a neighborhood around a reference distribution, offering robust guarantees across plausible inputs rather than individual adaptation. This is especially relevant when prior knowledge or public data (e.g., a shared $P_0$) is available to guide the analysis.\n\n\nThat said, although the two formulations address different goals, they share structural similarities. As noted in the related work section, the neighborhood $N(P_0)$ in our framework aligns with that in Feldman et al.’s instance-optimality. We will add this comparison to the appendix to clarify their conceptual and technical connections."}]

Author rebuttal:

Meta-review: This paper studies the problem of generating a sample from a distribution given to a user under the constraints of local differential privacy. The problem was studied/introduced in two previous works. This work extends previous work in two directions: (a) goes beyond pure DP  with optimal global minimax risk (b) it studies local minimax risks of private samplers, modeled as the knowledge of a "public" distribution P_0. The errors of the proposed algorithms are validated numerically. This is a nice technical and conceptual progress on a relatively natural problem. The main weakness is that there are no compelling motivating problems that would allow one to evaluate the significance of any of the improvements. Still given the importance of sampling problems in modern ML the insights given in this work may prove useful.
Decision: Accept (poster)