Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
Sajani Vithana 1 Sangwon Jung 2 Haoyang Hu 3 Viveck R. Cadambe * 3 Flavio P. Calmon * 1 Haewon Jeong * 4 5
Abstract
2025). The resulting synthetic dataset can be freely shared and reused in downstream tasks with no privacy leakage.
Differential privacy (DP) imposes fundamental trade-offs between privacy and statistical fidelity in synthetic data generation. While access to public data has been shown to improve these tradeoffs empirically, existing approaches use public data only indirectly, through pre-processing (e.g., using pre-trained generative models) or postprocessing steps (e.g., matching target statistics estimated from public datasets), while relying on domain-agnostic DP mechanisms. In this work, we lay the theoretical framework to study the principled incorporation of public data into DP mechanisms themselves. We consider normalized histograms as distribution estimators and characterize the asymptotically optimal domain-aware privacy mechanism within a specific class of DP mechanisms. We introduce P UB M IX, a publicdata-aware DP mechanism that can be used in histogram-based data synthesis pipelines. Our experiments demonstrate that P UB M IX significantly improves synthetic data generation quality compared to domain-agnostic privacy mechanisms.
To improve utility of DP synthetic data generation, several works have explored leveraging auxiliary public data from the same domain, typically incorporating it through preprocessing or post-processing steps. Examples include pretraining generative models on public data (Ghalebikesabi et al., 2023), using public data to inform which statistics to measure (Fuentes et al., 2024; Liu et al., 2021a), and post-processing synthetic data to align with public data constraints (Slavkovic & Reimherr, 2020; Wang et al., 2023). In all these approaches, however, the underlying DP mechanism (how randomness is injected to ensure privacy) remains domain-agnostic, typically based on Gaussian or Laplace noise (Dwork et al., 2006). We propose a fundamentally different paradigm for incorporating public data: using it directly to design how randomness is injected to achieve privacy in data synthesis. By constructing domain-aware noise distributions informed by public data, we obtain DP mechanisms that achieve improved privacy–utility trade-offs compared to domain-agnostic privacy mechanisms. DP synthetic data generation typically involves estimating the distribution of a private dataset, perturbing the estimate to ensure privacy, and sampling synthetic data from the perturbed distribution (McKenna et al., 2021; Frigerio et al., 2019; Pfitzner & Arnrich, 2022; McKenna et al., 2022; 2019; Hardt et al., 2012; Zhang et al., 2017). Standard domainagnostic DP mechanisms, such as Laplace or Gaussian noise, perturb the estimated private distribution in arbitrary directions on the probability simplex. In contrast, we show that public data can be leveraged to identify optimal directions along which the private distribution should be perturbed.
1. Introduction Modern data-driven systems require access to large, diverse datasets in order to train, evaluate, and validate models. In many of these settings, the underlying data consists of sensitive records such as patient histories or financial transactions that cannot be directly shared or reused due to privacy regulations. Differentially private (DP) synthetic data generation offers a solution to this challenge by constructing a synthetic dataset that preserves the statistical properties of the original private data with formal DP guarantees (Ponomareva et al.,
In this paper, we develop a theoretical framework for analyzing a linear mixing-based class of domain-aware DP mechanisms for private data synthesis, considering normalized histograms as private distribution estimators. In this canonical setting, we characterize the asymptotically optimal noise distribution, demonstrating that it can be approximated by a floor-raised (Gallager, 1968) version of the public distribution. From a theoretical stand point, these insights serve as a foundational step toward developing domain-aware DP mechanisms for complex distribution estimators used
*Senior authors in alphabetical order. 1 School of Engineering and Applied Sciences, Harvard University, Allston, MA, USA. 2 Trillion Labs, Seoul, South Korea. 3 School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, GA, USA. 4 Department of Electrical and Computer Engineering, University of California, Santa Barbara, USA. 5 Flatiron Institute, New York, USA. Correspondence to: Sajani Vithana <[email protected]>. Preprint. July 21, 2026.
1
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
in synthetic data generation (see Sec. 3.2). From a practical perspective, our analysis directly informs the design of P UB M IX, a domain-aware DP mechanism for histogram sampling that can replace standard Gaussian or Laplace mechanisms in existing histogram-based synthesis pipelines (Lin et al., 2024; Xie et al., 2024; Abacha et al., 2025; Zhang et al., 2025) for improved utility (see Sec. 5.2). Our key contributions are:
setting by incorporating public data into the problem formulation, while restricting to a more structured setting (linear mixing-based DP mechanisms) to make public-data integration tractable. Existing linear mixing methods include variants of private prediction (Flemings et al., 2024; Ginart et al., 2022) that serve as alternatives to existing DP training methods. Instead of privatizing the model itself, these methods enforce privacy at inference time by perturbing the model’s output. In LLMs, this typically involves mixing or projecting the private model’s next-token distribution toward a public distribution to limit leakage from memorized private data. While both P UB M IX and private prediction involve linear mixing and public distributions, they differ fundamentally in goal and technical design (More details in App. A).
• We introduce a principled framework for leveraging public data to construct domain-aware noise distributions that improve the privacy-utility trade-off in DP data synthesis compared to domain-agnostic privacy mechanisms. • We provide an information-theoretic analysis of the privacy–utility trade-off in DP histogram sampling within a class of mechanisms and characterize the asymptotically optimal domain-aware privacy mechanism.
DP histograms are a core primitive underlying many synthesis pipelines, with work spanning basic privatization (Dwork & Roth, 2014; Dwork et al., 2006), hierarchical constructions (Qardaji et al., 2013), and adaptive/improved binning (Hay et al., 2010). Recent private evolution methods and their federated learning extensions (Abacha et al., 2025; Hou et al., 2025) further highlight the practical role of histogram sampling, demonstrating strong empirical performance across modalities when combined with foundation models. P UB M IX can be incorporated as a drop-in privacy mechanism within the histogram-based pipelines.
• We propose P UB M IX, a DP histogram sampling mechanism that incorporates domain-aware noise and serves as a drop-in privacy module for histogram-sampling-based synthetic data generation. 1.1. Related Work DP synthetic data generation has been studied across modalities including tabular data, text, and images. Existing approaches include (i) statistical methods that privately release noisy summary statistics to fit distributional models (McKenna et al., 2022; Hardt et al., 2012; Cai et al., 2021; Zhang et al., 2017; McKenna et al., 2021), and (ii) training deep generative models with DP-SGD (Frigerio et al., 2019; Dockhorn et al., 2023; Yue et al., 2023). Complementary paradigms include PATE (Papernot et al., 2018; Long et al., 2021), which trains teachers on disjoint private partitions and aggregates their noisy predictions to label public data for synthesis; Private Evolution (Lin et al., 2024; Xie et al., 2024; Tran et al., 2026), which iteratively samples from (hierarchical) histograms to produce synthetic datasets; and variants of private prediction (Amin et al., 2024; Tang et al., 2024), which synthesize text by privately aggregating nexttoken predictions from LLMs prompted with sensitive examples. See (Ponomareva et al., 2025) for a comprehensive survey. While some methods leverage public data to reduce privacy cost (Fuentes et al., 2024; Liu et al., 2021a), the underlying DP mechanisms remain largely domain-agnostic (Gaussian, Laplace, or exponential mechanisms). In contrast, we introduce the concept of domain-aware privacy mechanisms.
2. Problem Formulation Let Dprv = {x1 , . . . , xn } ⊆ X n denote a private dataset where X is a discrete sample space with |X | = d. Each xi ∈ Dprv is sampled i.i.d. from an underlying distribution Pprv ∈ ∆d , where ∆d is the probability simplex over X . Let Dpub = {vi }ℓi=1 ⊆ X ℓ be a public dataset from the same domain as Dprv , sampled i.i.d from an underlying distribution Ppub ∈ ∆d . We estimate Pprv and Ppub using the normalized histograms of Dprv and Dpub over X , denoted by P̄prv and P̄pub , respectively. Our goal is to generate a synthetic dataset Dsyn = {yi }m i=1 consisting of m samples that: (i) satisfies DP with respect to Dprv , (ii) is statistically close to Dprv . For this, we design a synthetic data distribution Psyn ∈ ∆d , from which we draw m samples i.i.d. to obtain the synthetic dataset Dsyn . Specifically, we consider synthetic distributions of the form: Psyn = (1 − β)P̄prv + βPnse
(1)
where β ∈ [0, 1] is a mixing coefficient and Pnse ∈ ∆d is a noise distribution. β and Pnse are globally known fixed parameters that are independent of the private data Dprv .
DP multi-sampling provides sample-complexity bounds for drawing independent samples from a given private distribution under DP, covering broader distribution families (Cheu & Nayak, 2025). We extend the DP multi-sampling
Our goal is to find the optimum parameters β and Pnse in (1) that achieves the maximum utility while satisfying DP. When the mixing parameter β = 0, we have Psyn = P̄prv , 2
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
(a) P UB M IX
(b) L IN M IX
(d) Comparison of TV(P̄prv , Psyn )
(c) Gaussian Mechanism
Figure 1. Comparison of P UB M IX, L IN M IX, and the Gaussian Mechanism for differentially private histograms. (a)–(c) provide a geometric illustration of the perturbations in the probability simplex for (a) P UB M IX, (b) L IN M IX, and (c) the Gaussian mechanism. (d) shows the total variation distance between (P̄prv , Psyn ) as a function of the number of synthetic samples m, for P UB M IX, L IN M IX, and the Gaussian mechanism for n = 57717, ε = 5, δ = 1/n based on the 2023 ACS PUMS dataset.
which is ideal for utility but provides no privacy guarantee. The other extreme, β = 1, yields Psyn = Pnse , and the generated synthetic data are independent of the private dataset, resulting in a substantial loss of utility while ensuring perfect privacy. Accordingly, for a fixed noise distribution Pnse we first identify the smallest β that satisfies DP, and then optimize Pnse to obtain the best achievable privacy–utility trade-off. The resulting Pnse determines the optimal direction along which the private distribution P̄prv should be perturbed. Here, Pnse will depend on the public data, as we will see shortly. First, we formally define the privacy constraint and the utility metric.
that datasets drawn from the same domain induce distributions that are close to each other on the probability simplex with high probability. We therefore seek a Pnse that are optimized for distributions in Bγ,P̄pub . Concretely, as we describe next, we optimize Pnse considering the worst-case private distribution within Bγ,P̄pub .1 An optimization formulation for mechanism design: Given a target (ε, δ), a public distribution P̄pub , and a proximity parameter γ, our goal is to find the optimal noise distribution Pnse and mixing coefficient β in (1) that satisfies the privacy constraint in (2) while maximizing utility. The optimization problem we solve to obtain these parameters is given by: (︂ )︂ min min max TV P̄prv , Psyn
Privacy constraint: We consider (ε, δ)-DP of the m gen′ erated synthetic samples Dsyn . Let Dprv and Dprv be any two neighboring datasets that differ in only one data entry. ′ Let Psyn and Psyn be the corresponding synthetic distributions from (1) for any fixed β ∈ [0, 1] and Pnse ∈ ∆X . Then, the (ε, δ)-DP constraint is given by,
Pnse ∈∆d
s.t.
P̄prv ∈Bγ,P̄
pub
′ P(Dsyn ∈ S) ≤ eε P(Dsyn ∈ S) + δ, ′ ∀S ⊆ X m , ∀Dprv , Dprv
′ P(Dsyn ∈ S) ≤ eε P(Dsyn ∈ S) + δ, ′ ∀S ⊆ X m , ∀Dprv , Dprv
β∈[0,1]
(3)
∗ We denote the parameters that solve (3) as (β ∗ , Pnse ). 2
(2)
′ where Dsyn and Dsyn correspond to the m i.i.d. samples ′ drawn from Psyn and Psyn .
∗ P UB M IX: Once the parameters β ∗ and Pnse are obtained, for any given Dprv , we compute Psyn = (1 − β ∗ )P̄prv + ∗ β ∗ Pnse using the corresponding P̄prv , and draw m samples from Psyn as private synthetic data Dsyn . We call this mechanism P UB M IX, and it is outlined in Alg. 1.
Utility: The utility of Dsyn is defined as the total variation (TV) distance between P̄prv and Psyn , i.e., TV(P̄prv , Psyn ).
Why use P UB M IX instead of just adding noise to histograms? Standard DP histogram mechanisms (Dwork & Roth, 2014) add i.i.d. Gaussian or Laplace noise to each histogram bin to achieve DP. Since the noise is zeromean and independent across bins, each bin can increase
The admissible set: To select a noise distribution Pnse in (1), we define an admissible set of private distributions close to the public distribution P̄pub . This set is fixed and independent of the given private data Dprv . We define the admissible set as all distributions within a γ-TV ball around P̄pub :
1
If the private distribution of Dprv lies outside Bγ,P̄pub (which cannot be verified a priori), P UB M IX still satisfies DP. However, a weaker utility guarantee will be achieved compared to (3). 2 ∗ The parameters β ∗ and Pnse in P UB M IX are not derived from the given private dataset. They are pre-computed parameters based on the worst case private distribution within a γ-TV ball around P̄pub (see (3)), and are independent of the given private dataset.
Bγ,P̄pub = {P ∈ ∆d : TV(P, P̄pub ) ≤ γ} for some proximity parameter γ ∈ (0, 1], independent of Dprv . The parameter γ is chosen based on public knowledge (see Sec. 5). The key motivation for this definition is 3
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
or decrease arbitrarily. When normalized to obtain a probability distribution, the perturbed histogram can move in arbitrary directions on the probability simplex relative to the non-private distribution. This domain-agnostic approach does not consider which perturbation directions optimize the privacy-utility trade-off for the given data domain (Fig.1c). In contrast, P UB M IX leverages public data from the same domain to identify a principled direction in which to perturb P̄prv , yielding a synthetic distribution Psyn that better preserves utility while still satisfying DP (Fig.1a).
Minimum mixing weight (details in Theorem 4.1): Given a noise distribution Pnse , privacy parameters ε, δ, number of synthetic samples m, and private dataset size n, there exists a threshold βmin such that any β ≥ βmin satisfies (ε, δ)-DP. Moreover, 1) βmin is a function of ε, δ, m, n and Pnse . 2) βmin is increasing in m. 3) βmin depends on Pnse only through its two smallest probability masses.
A key feature of P UB M IX is sample dependency. Most existing DP synthesis methods incur a high privacy cost by releasing the entire privacy-protected distribution Psyn (Xie et al., 2024; Lin et al., 2024). For instance, in existing DP histogram-based synthesis methods that add Gaussian or Laplace noise to each of the d bins independently, TV(P̄prv , Psyn ) increases linearly with d (Qardaji et al., 2013). However, many applications require only a finite number of synthetic samples, and not the full distribution.
Intuition: For given parameters ε, δ, m, n, Pnse , the privacy constraint in (2) can be equivalently written as: ⊗m ′⊗m Eeε (Psyn ∥Psyn ) ≤ δ,
′ ∀Dprv , Dprv
(4)
where Eeε (P ∥Q) denotes the hockey-stick divergence between distributions P and Q (or the Eγ divergence with γ = eε ), and P ⊗m denotes the m-fold product distribution corresponding to m i.i.d. draws of P . Solving (4) with equality yields the minimum mixing weight βmin for the chosen Pnse . Importantly, since neighboring private P datasets differ in exactly one sample, the ratio Psyn is ex′ syn actly 1 in all but (at most) two coordinates. Leveraging this 2-point sparse structure tightens the privacy accounting compared to existing DP histogram release methods.
We show that, when the goal is to release only m synthetic samples from the histogram rather than the histogram itself, it is possible to construct a synthetic sampling distribution Psyn that is significantly closer to P̄prv , resulting in more accurate synthetic data (Fig. 1-d). The key insight is that the normalized histogram of a private dataset Dprv differs from ′ that of any neighboring dataset Dprv in at most two coordinates. Specifically, as n denotes the number of samples in Dprv , replacing a single sample causes one bin to increase by 1/n while another bin decreases by 1/n. When releasing an entire DP histogram, this sparsity of the neighboring difference cannot be leveraged, and noise must be injected across all d coordinates. However, when releasing only samples, and working under (ε, δ)-DP, this sparse structure can be leveraged, yielding tighter privacy accounting.
For a given Pnse , the value of βmin specifies the minimum separation that Psyn must maintain from P̄prv to satisfy DP. Since the information leakage increases with the number of synthetic samples released, βmin increases with m (see Fig. 2). The next property that βmin depends on Pnse only through its two smallest probability masses is also intuitive: Since the same mixing weight β is applied to every coordinate in (1), the coordinates with the smallest noise masses in Pnse receive the least added randomness. The worst case therefore occurs when the two coordinates that differ in neighboring private histograms coincide with the indices of the two smallest entries of Pnse . Consequently, letting Nmin1 = mini Pnse (i) and Nmin2 = mini̸=i1 Pnse (i) where i1 = arg mini Pnse (i), the pair (Nmin1 , Nmin2 ) determines the smallest β for which DP is satisfied. Since βmin depends on Pnse only through its two smallest probability masses Nmin1 and Nmin2 , we write βmin = βmin (Nmin1 , Nmin2 ) to make it explicit.
3. Main Results: Overview and Intuition Before presenting the full mathematical treatment of how to solve (3) in Section 4, we first provide a high-level intuition for our solution and how P UB M IX leverages public data. 3.1. Technical overview Recall that P UB M IX constructs the synthetic dataset Dsyn by drawing m samples from a carefully designed distribu∗ ∗ tion Psyn = (1 − β ∗ )P̄prv + β ∗ Pnse . Here, β ∗ and Pnse are the optimal parameters. To solve the optimization in (3), we first fix a noise distribution Pnse and find the minimum mixing weight βmin (for this specific Pnse ) for which the DP constraint in (2) is satisfied.
Consider Nmin1 = Nmin2 = Nmin . The behavior of βmin (Nmin , Nmin ) for 0 ≤ Nmin ≤ d1 is shown in Fig. 2, where d = |X |. βmin (Nmin , Nmin ) is decreasing in Nmin as a larger value of Nmin corresponds to a larger baseline noise being injected across all coordinates of P̄prv . Since more noise is already guaranteed at each coordinate, a smaller mixing weight β suffices to satisfy DP. 4
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
Having characterized the minimum mixing weight for a fixed noise distribution Pnse , we next optimize over Pnse . Asymptotically optimum noise distribution (details in Theorem 4.2): For a given public distribution P̄pub and γ > 0, the asymptotically optimum noise distri∗ bution Pnse , characterized in Theorem 4.2, is a floorraised version of P̄pub with an optimal threshold t. Floor-raising a distribution P̄pub with threshold t raises all coordinates below t at least up to t, and compensates by reducing the mass from coordinates above t in a way that preserves normalization (see examples in Fig. 3). Moreover, the optimum threshold t is a function of γ, P̄pub , ε, δ, m and n.
Figure 2. Comparison of minimum mixing weight βmin for different numbers of synthetic samples m and minimum noise components Nmin with n = 1200, d = 1000, ε = 5 and δ = 1/n.
Intuition: To determine the optimum noise distribution, we first observe that TV(P̄prv , Psyn ) = βTV(P̄prv , Pnse ). Then, the optimization in (3) can be upper bounded by: (︄ )︄ min βmin (Nmin1 , Nmin1 )
Pnse ∈∆d
max TV(P̄prv , Pnse )
P̄prv ∈Bγ,P̄
(a) Original: P
pub
(5)
(c) MIFR(P, t)
Figure 3. Two instances of floor-raising: (a) original PMF, (b) Water-filling: raises smaller masses to t and removes the added mass uniformly from larger masses (Def. 4.3), (c) Maximum Invariant Floor Raising (MIFR): raises smaller masses to t and removes the added mass Madd from larger ones to maximize the unchanged probability mass with respect to the original (Def. 4.4).
since the mixing weight β is chosen independently of P̄prv and βmin (Nmin1 , Nmin2 ) is decreasing in Nmin2 . The op∗ timal Pnse in (5) is an asymptotic optimizer for (3) since (5) converges to (3) as d → ∞. Details in Sec. 4. Consider the two terms in (5). βmin (Nmin1 , Nmin1 ) is minimized when Nmin1 is maximized (see Fig. 2). Thus, the Pnse minimizing the first term is the uniform distribution, where Nmin1 = d1 . Now consider the second term (inner max). For any given Pnse , the inner max is achieved by some P̄prv on the boundary of Bγ,P̄pub . Therefore, the minmax TV distance is achieved by the Pnse at the L1 Chebyshev center3 of Bγ,P̄pub (close to P̄pub ). The first term pushes Pnse toward the center of the simplex ∆d (the uniform distribution), while the second term pushes it toward the Chebyshev center of Bγ,P̄pub , which lies close to P̄pub . ∗ The optimal Pnse balances these two effects: it stays close to P̄pub to minimize the worst-case TV term, while simultaneously increasing Nmin1 to reduce the βmin (Nmin1 , Nmin1 ) term. In Theorem 4.2, we show that the resulting optimum ∗ Pnse is a floor-raised version of P̄pub characterized by a ∗ linear program. Moreover, we show that Pnse can be approximated by one of two easily computable floor-raising mechanisms explained in Fig. 3. These floor-raising operations slightly move P̄pub towards the uniform distribution (details in App. B), thereby increasing Nmin1 and lowering βmin (Nmin1 , Nmin1 ). At the same time, it preserves proximity to the minimizer of the inner maximization term.
tion to (3) when no public data is available, i.e., Bγ,P̄pub = ∆d . For this, we again analyze the two terms in (5) separately. The inner maximization in (5) is attained by a P̄prv at an extreme point of the simplex (e.g., a corner of the triangle in Fig. 1). Thus, the noise distribution minimizing the inner maximum term in (5), i.e., the minmax optimal distribution, is the uniform distribution, which is at the center of the simplex. Now, consider the βmin (Nmin1 , Nmin1 ) term in (5). Since βmin (Nmin1 , Nmin1 ) is decreasing in Nmin1 , it is minimized when Nmin1 = d1 . Both of these facts imply ∗ that the objective in (5) is minimized by Pnse = d1 1d , i.e., the uniform distribution (see Corollary 4.6). We call this mechanism L IN M IX. However, this solution is driven by the worst-case private distribution, which is a point mass at one of the corners of the simplex. A point mass is a highly atypical and prac∗ tically irrelevant distribution. Optimizing Pnse based on ∗ a point mass forces Pnse to be far from most realistic private distributions P̄prv , which results in a large TV distance between the private and synthetic distributions, as shown in Fig. 1. To mitigate this, we leverage public data from the same domain and solve (3) with Bγ,P̄pub ⊂ ∆d . This results in P UB M IX, which achieves significantly improved performance (red curves).
Significance of public data: Consider the asymptotic solu3
(b) Water-filled(P, t)
L1 -Chebyshev center of a set Q: arg minc maxx∈Q ∥x−c∥1 .
5
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
Algorithm 1 P UB M IX
with [x]+ = max{x, 0}, and h2 (β, ε, n, m, Nmin1 , Nmin2 ) is the same as h1 (·) with Nmin1 and Nmin2 swapped.
Input: : Private distribution P̄prv , public distribution P̄pub , private dataset size n, required sample size m, proximity parameter γ, privacy parameters (ε, δ) Output: : Synthetic dataset Dsyn ∗ 1: Compute near-optimal noise distribution Pnse and mix∗ ing weight β using P̄pub , γ, ε, δ, m, n (Remark 4.5) 2: Form the synthetic distribution:
The proof of Theorem 4.1 is given in App. C. Since we need the mixing weight β to be as small as possible for optimal utility (see Fig. 1a), for any given Pnse , the optimum mixing weight is the corresponding βmin (Nmin1 , Nmin2 ) from Theorem 4.1. ∗ Next, we analyze the optimal noise distribution Pnse . To this end, we provide an asymptotically optimal solution to (3) in Theorem 4.2. The original problem in (3) can be equivalently written as,
∗ Psyn ← (1 − β ∗ ) P̄prv + β ∗ Pnse
3: Draw m i.i.d. samples from Psyn to obtain Dsyn 4: return Dsyn
min
Pnse ∈∆d
3.2. Beyond Histograms
max
TV(P̄prv , Psyn ) (8)
P UB M IX extends naturally to general discrete distribution estimators that satisfy a bounded sensitivity condition, [i] ′[i] namely, maxi |P̄prv − P̄prv | ≤ s for some s > 0, where [i] P̄prv denotes the i-th coordinate of P̄prv . In this setting, the domain-aware noise distribution continues to take the form of a floor-raised version of P̄pub , while the minimum mixing weight β is increased as we lose the two-point sparsity structure of neighboring histograms (see Appendix H). The same principles suggest potential extensions of P UB M IX to parametric distribution families, such as Gaussian mixtures.
which can be bounded as: min
Pnse ∈∆d
≤
min
max
β∈[0,1] P̄prv ∈Bγ,P̄ pub β≥βmin (Nmin1 ,Nmin2 )
min
min
max
TV(P̄prv , Psyn ) TV(P̄prv , Psyn )
Pnse ∈∆d β∈[0,1] P̄prv ∈Bγ,P̄ pub β≥βmin (Nmin1 ,Nmin1 )
(9) as Nmin1 ≤ Nmin2 and β(Nmin1 , Nmin2 ) is nonincreasing in both Nmin1 and Nmin2 (see Lemma C.5). In Theorem 4.2, we provide the solution to the upper bound ∑︁ [i] in (9). Notice that i Pnse = 1 requires:
4. Main Results: Technical Details In this section, we formalize the arguments made in Sec. 3. We begin by deriving a condition on the mixing weight β that guarantees DP for a given noise distribution Pnse . Theorem 4.1 (Feasible mixing weights β). Fix ε > 0, δ ∈ (0, 1), private dataset size n, and the required number of synthetic samples m ≥ 1. Let Pnse ∈ ∆d be any noise distribution and denote the two smallest probability masses of Pnse by Nmin1 and Nmin2 , with Nmin1 ≤ Nmin2 . Then, for every β ≥ βmin (Nmin1 , Nmin2 ), the m synthetic samples drawn from Psyn in (1) satisfy the DP constraint in (2), where βmin (Nmin1 , Nmin2 ) is the solution to β in:
0 ≤ Nmin1 ≤ Nmin2 ≤
1 − Nmin1 d−1
Theorem 4.2 (Asymptotically optimal parameters:). Let γ ∈ (0, 1] be a constant and let P̄pub ∈ ∆d be a public distribution. Fix the privacy parameters ε > 0, δ ∈ (0, 1) and the required number of synthetic samples m ≥ 1. Then, min
(6)
Pnse ∈∆d
where
min
max
β∈[0,1] P̄prv ∈Bγ,P̄ pub β≥βmin (Nmin1 ,Nmin1 )
TV(P̄prv , Psyn )
= min1 βmin (t, t)f (t)
(11)
0≤t≤ d
h1 (β, ε, n, m, Nmin1 , Nmin2 ) (︃ )︃m−λ−µ ∑︂ m! 1−β = 1−β(Nmin1+Nmin2)− λ!µ!(m−λ−µ)! n
where f (t) is the solution to the following linear program: f (t) =
λ,µ≥0 λ+µ≤m
[︄(︃ ]︄ )︃λ (︃ )︃µ 1−β 1−β µ ε λ βNmin1+ (βNmin2) −e βNmin2+ (βNmin1) n n
(10)
which makes Nmin2 → Nmin1 for larger d, resulting in βmin (Nmin1 , Nmin2 ) → βmin (Nmin1 , Nmin1 ). Thus, the solution to the upper bound in (9) is asymptotically optimal for (3) (see App. D.1 for rigorous proof).
max{h1 (β, ε, n, m, Nmin1 , Nmin2 ), h2 (β, ε, n, m, Nmin1 , Nmin2 )} = δ
min
β∈[0,1] P̄prv ∈Bγ,P̄ pub β≥βmin (Nmin1 ,Nmin2 )
min
Pnse ∈∆d , r∈R
s.t.
r
r + Pnse (S) ≥ min{P̄pub (S) + γ, 1}, ∀S ⊂ [d],
+
(7) 6
[i] Pnse ≥ t, ∀i,
1 ≤ |S| ≤ d − 1 1Td Pnse = 1
(12)
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
∑︁ with the notation P (S) = i∈S P [i] . The corresponding ∗ optimum Pnse is the minimizing Pnse of (12) with t = t∗ ∗ where t = arg min0≤t≤ d1 βmin (t, t)f (t). The optimum β ∗ is given by β ∗ = βmin (t∗ , t∗ ).
entries above t to decrease. WF spreads the required mass removal across all entries above t in a uniform “leveling” manner until some reach t. In contrast, MIFR concentrates the mass removal on a carefully chosen subset of entries above t so as to keep as many coordinates unchanged as ∑︁ possible, i.e., it maximizes the invariant mass i:Bi =Ai Ai . An illustration of Def. 4.3 and Def. 4.4 is given in Fig. 3.
The proof of Theorem 4.2 is given in App. E. We next ∗ develop a (sub-optimal) approximation for Pnse in (12), on which P UB M IX is built. For this, we first define Water-filling and Maximum-invariance floor raising.
Remark 4.5. For given parameters ε, δ, m, n, P̄pub , γ, an ∗ approximation to the Pnse in Theorem 4.2 is given by, ⎧ (︁ )︁ ⎪ P̄pub , t1 ) ⎨MIFR(P̄pub , t1 ), g MIFR( (︁ )︁ ∗ P̂nse = ≤ g WF(P̄pub , t2 ) ⎪ ⎩ WF(P̄pub , t2 ), o.w.
Definition 4.3. [Water-Filling (WF)] Let A be a probability mass function (PMF) on Ω = {ω1 , . . . , ωd } with Ai := A(ωi ). Assume without loss of generality that the indices are arranged such that A1 ≤ A2 ≤ . . . ≤ Ad . Let t ∈ [0, 1/d] be any constant satisfying A1 ≤ . . . ≤ Ak ≤ t < Ak+1 ≤ . . . ≤ Ad for some k < d. Then, the t-water-filled version of A, denoted by B = WF(A, t) is given by, Bi = max{t, Ai − τ }, t(k+ℓ)−
∑︁k+ℓ
∀i ∈ {1, . . . , d}
where t1 , t2 are optimized thresholds, and g(Pnse ) = βmin (Nmin1 , Nmin1)
(13)
[i]
A
∗ ∗ β̂ ∗ = βmin (Nmin , Nmin ) 1 1 ∗[i]
∗ ∗ where Nmin = mini P̂nse . In most cases, P̂nse coincides 1 ∗ with Pnse from Theorem 4.2, but it is generally sub-optimal (see App. F for more details).
Definition 4.4. [Maximum-Invariance Floor Raising (MIFR)] Let A be a probability mass function on Ω = {ω1 , . . . , ωd } with Ai := A(ωi ). Fix t ∈ [0, 1/d]. The maximum-invariance floor raised version of A at level t is given by B = MIFR(A, t) with coordinates ⎧ ⎪ i ∈ L, ⎨t, Bi = bi , i ∈ U ⋆ , ⎪ ⎩ Ai , i ∈ / L ∪ U ⋆,
∗ The Key insight from Remark 4.5 is that P̂nse is always a floor-raised version of P̄pub , where both MIFR(P̄pub , t1 ) and WF(P̄pub , t2 ) raise small elements of P̄pub to their respective thresholds and redistribute probability mass from larger elements. This design balances two objectives: since P̄prv and P̄pub come from the same domain with typically small TV(P̄pub , P̄prv ), choosing Pnse close to P̄pub is beneficial. However, many elements in P̄pub can be small (even zero), which would add minimal noise to corresponding [i] P̄prv elements and require a larger mixing weight β to maintain privacy, pushing Psyn too close to P̄pub (not to P̄prv ). ∗ resolves this tradeoff by remaining close to P̄pub while P̂nse floor-raising smaller probabilities to guarantee a sufficient [i] Nmin1 = mini Pnse , which allows a smaller β and yields a Psyn that is closer to P̄prv .
where L := {i : Ai ≤ t} and Lc := {i : Ai > t}. The donor set U ⋆ ⊆ Lc is defined as ∑︂ ∑︂ ∑︂ U ⋆ = arg minc Ai s.t. (Ai −t) ≥ (t−Ai ). i∈U
i∈U
i∈L
Finally, the values {bi }i∈U ⋆ satisfy bi ≥ t, ∀i ∈ U ⋆ and ∑︂ ∑︂ (Ai − bi ) = (t − Ai ), i∈U ⋆
TV(P̄prv , Pnse ) pub
for any Pnse with Nmin1 = mini Pnse . The corresponding minimum mixing weight is given by,
i i=1 where τ = is a unique constant satisfying d−k−ℓ ∑︁d i=1 Bi = 1 and Ak+ℓ −t ≤ τ < Ak+ℓ+1 −t for a unique ℓ ∈ {0, 1, . . . , d − k − 1}.
U ⊆L
max
P̄prv ∈Bγ,P̄
To see the significance of using domain information via public data, consider the solution to (3) when no public dataset Dpub is available, i.e., when Bγ,P̄pub = ∆d .
i∈L
so that the total mass removed from indices in U ⋆ exactly matches the total mass added on L.
Corollary 4.6 (Asymptotic optimality with no Dpub ). For any Dprv , m ≥ 1, ε > 0 and δ ∈ (0, 1), the asymptotic solution to (3) with Bγ,P̄pub = ∆d is given by,
Both WF and MIFR (Def. 4.3 and 4.4) raise every probability mass below the threshold t up to t. The extra mass added in this step is then removed from entries above t, while ensuring no entry is reduced below t. In this way, both procedures produce a modified PMF B that satisfies Bi ≥ t and attains the minimum possible TV distance to the original PMF A. The two methods differ in how they choose which
min
Pnse ∈∆d
min
max TV(P̄prv , Psyn )
β∈[0,1] P̄prv ∈∆d β≥βmin (Nmin1 ,Nmin1 )
= (1 − 1/d) βmin (1/d, 1/d) 7
(14)
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation ∗ and the corresponding optimum Pnse and β ∗ are given by, ∗ Pnse =
1 1d d
and
β ∗ = βmin (1/d, 1/d)
(15)
where 1d is the all ones vector of size d. Corollary 4.6 (proof in App. G) shows that without domain information (i.e., no public data from the same domain as Dprv ), the optimal noise distribution is uniform and Psyn is formed by mixing uniform noise with P̄prv . We call this mechanism L IN M IX. This effectively pulls Psyn toward the uniform distribution and away from P̄prv . In contrast, when relevant public data is available, Theorem 4.2 and Remark 4.5 establish that the optimal noise distribution is close to P̄pub . Since P̄pub and P̄prv share similar structural properties, linearly combining them preserves much of this structure, allowing Psyn to remain closer to P̄prv while still satisfying the privacy constraint.
Figure 4. Comparison of the total variation (TV) distance between P̄prv and the empirical distribution of the synthetic dataset Dsyn for n = 57,717, ε = 5, and δ = 1/n on the PUMS dataset.
5. Experiments In the first part of this section, we illustrate the core ideas of P UB M IX with a simplified setting. In the second part, we integrate P UB M IX into state-of-the-art DP synthetic data generation pipelines (histogram-based) and show improved performance.4 First, we explain how the proximity parameter γ is chosen in both experimental settings. γ captures the variation of the domain data: if distributions estimated from different public datasets in the same domain vary substantially, γ should be larger. If they are similar, a smaller γ is appropriate. In our experiments, we either collect k public datasets from the same domain, or randomly partition the available public dataset into k folds, compute pairwise TV distances between the fold distributions, and use the distribution of these distances to estimate γ.
Figure 5. Accuracy of a regression model trained on synthetic data by P UB M IX, L IN M IX, and the Gaussian mechanism, measured relative to a model trained on real data from the PUMS dataset.
Fig. 4 compares the TV distance between private distribution and the empirical distribution of the generated synthetic data. L IN M IX performs well for small m but degrades as m increases, while P UB M IX avoids this degradation by leveraging public data. We assess downstream utility by training a random forest regressor to predict English proficiency (values from 1-5) using the remaining features, with the model trained on the generated synthetic samples. Here, we use 80% of Texas data as Dprv to generate the synthetic samples. We then use the remaining 20% of Texas data as the test set to evaluate the performance of the model trained on the synthetic data. Figure 5 compares P UB M IX against a non-private model trained directly on Dprv , the Gaussian baseline, and L IN M IX (no Dpub ).
5.1. Illustrating the Core Concepts In this section, we use a simplified setting in which the normalized histogram of the private data serves as the distribution estimate, and P UB M IX is used to directly sample synthetic data. To make this setting tractable, we use the 2023 ACS Public Use Microdata Sample (PUMS) dataset (U.S. Census Bureau, 2024) by restricting each record with 7 features: race, sex, class of work, marital status, education level, disability status, and English proficiency. We analyze the quality of the P UB M IX-generated samples in terms of TV distance and downstream-task performance by comparing with the standard Gaussian mechanism and the setting with no public data (L IN M IX). We use Texas data as Dprv and California data as Dpub . 5
5.2. Evaluation on Existing Pipelines We next evaluate P UB M IX on two modalities, tabular and text, to demonstrate that it can be used as a drop-in replacement for the DP histogram sampling subroutine in existing state-of-the-art synthetic data generation pipelines. Concretely, we adopt Private Evolution (PE) based methods (Tran et al., 2026; Xie et al., 2024), which are recently proposed frameworks generating synthetic data through an iterative process: they repeatedly produce candidate variations of the data and then randomly samples from Gaussiannoised histograms obtained from the variations. In our experiments, we keep the PE pipeline unchanged and replace
4
Code available at: https://github.com/sajani-vithana/PUBMIX We set γ to the average pairwise TV distance among statelevel distributions from California, Colorado, Florida, and Utah. 5
8
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation Table 1. Downstream classification accuracy (%) on Person Activity under varying privacy budgets. We report mean ± std over multiple runs. Method
ε = 1.0
ε = 2.0
ε = 4.0
GEM (Liu et al., 2021b) PrivSyn (Zhang et al., 2021) GSD (Liu et al., 2023) AIM (McKenna et al., 2022) JAM-PGM (Fuentes et al., 2024) PMWpub (Liu et al., 2021a) TAB PE (Tran et al., 2026)
28.24± 0.43 27.40± 2.70 49.48± 0.27 56.77± 0.23 55.96± 0.24 49.21± 0.80 60.80± 0.54
28.51± 1.84 28.41± 2.03 50.00± 0.25 58.42± 0.11 56.51± 0.28 48.96± 1.05 63.22± 0.48
28.46± 0.40 28.06± 1.82 50.46± 0.54 59.12± 0.30 57.37± 0.23 49.37± 0.91 64.24± 0.45
P UB M IX
66.40± 0.49
66.47± 0.42
66.85± 0.08
Table 2. Utility on Yelp Reviews under varying privacy budgets. We report mean ± std over multiple runs. Category classification accuracy (%, higher is better) and Rating RMSE (lower is better). PE (ε = ∞) : Category 72.13%, RMSE 0.873. Metric
Method
ε=1
ε=2
ε=4
Category (↑)
PE (Xie et al., 2024) P UB M IX
71.67± 0.21 71.01± 0.17
70.69± 0.41 71.57± 0.34
69.93± 0.38 72.35± 0.20
Rating (↓)
PE (Xie et al., 2024) P UB M IX
0.90± 0.025 0.81± 0.016
0.91± 0.009 0.81± 0.022
0.89± 0.021 0.80± 0.039
This pattern shows that P UB M IX leverages related public data to improve utility under stronger privacy constraints.
only the internal DP sampling-from-histograms component with P UB M IX.
5.2.2. Text: Yelp Reviews Experimental setup. We consider a real-world text synthesis setting where the private dataset is Yelp reviews (Yelp Inc., 2023), and the public dataset is Google Local Reviews from 10 states (Li et al., 2022; Yan et al., 2023). This public dataset provides a realistic public signal from a related but non-identical distribution, reflecting practical scenarios where public web-scale reviews exist but do not exactly match the private domain. Yelp provides two downstream tasks that capture complementary aspects of utility. (i) Category classification: a trained classifier on the synthetic reviews predicts the business category. (ii) Rating prediction: a trained regressor predicts the star rating in {1, . . . , 5}. We report classification accuracy and the root mean squared error (RMSE) for the rating, on the test set.
5.2.1. Tabular: Person Activity Records Experimental setup. We use the Person Activity dataset (Vidulin et al., 2010), which contains sensor-based activity records collected from five users. To mimic a realistic deployment where related public data is available, we construct the private dataset Dprv using records from three users, and the public dataset Dpub using records from the remaining two users by splitting the original dataset. This split preserves the domain and task semantics while introducing a natural distribution shift across users, matching the intended use of public-data-guided sample generation. As our primary baseline, we adopt TabPE (Tran et al., 2026), a state-of-the-art DP synthetic data generator for tabular data. Importantly, TAB PE relies on a DP histogram-based sampling subroutine as a core primitive in its update procedure. Building on this modular structure, our main comparison is TAB PE+P UB M IX, where we only replace this DP histogram sampling component in TAB PE with P UB M IX while keeping all other components (e.g., model architecture, iterations, and optimization settings) unchanged. This experimental design isolates the benefit of P UB M IX as a drop-in sampling primitive. We also compare P UB M IX against additional tabular DP baselines, including GSD (Liu et al., 2023), AIM (McKenna et al., 2022), GEM (Liu et al., 2021b), P RIV S YN (Zhang et al., 2021), as well as JAM-PGM (Fuentes et al., 2024) and PWMpub (Liu et al., 2021a) that utilize public data. Following prior work (Tran et al., 2026), we evaluate synthetic data utility by training a downstream classifier on synthetic samples and reporting test accuracy of classification performance for human activity.
We adopt a PE variant method, tailored for DP text synthesis as our main baseline (Xie et al., 2024). We apply P UB M IX as a plug-in replacement in the DP sampling component of the PE pipeline, while keeping all remaining settings identical. Additional details (length constraints, model configuration, and training schedule) are provided in App. I. Results. Table 2 summarizes utility on Yelp across privacy budgets. Overall, P UB M IX improves the privacy-utility tradeoff over the PE baseline on both tasks. In particular, P UB M IX consistently reduces rating prediction error (RMSE) for all ε, indicating better preservation of the continuous rating signal under DP. These results suggest that public-guided DP sampling can enhance PE-based text synthesis without changing the rest of the pipeline.
6. Conclusion
Results. Table 1 reports downstream accuracy across privacy budgets. Across all ε ∈ {1, 2, 4}, TAB PE + P UB M IX achieves the best performance, consistently outperforming the PE baseline as well as all other DP tabular methods. Notably, the gains over PE are largest in the stricter privacy regime: PE+P UB M IX improves PE by +5.80 points at ε = 1 (66.60 vs. 60.80), and remains advantageous at ε = 2 and ε = 4 (+2.93 and +1.88 points, respectively).
In this paper, we introduced the concept of domain-aware DP mechanisms for synthetic data generation and provided a corresponding theoretical framework. For normalized histograms, we characterized the optimal domain-aware DP mechanism within a class of distribution mixing functions. To this end, we introduced P UB M IX, a public-data-aware privacy mechanism that can be used as a drop-in replacement for Laplace or Gaussian mechanisms in histogram9
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
based data synthesis pipelines. Empirically, we show that incorporating P UB M IX in existing data synthesis pipelines consistently improves the privacy–utility trade-off.
differentially private Markov random fields. Proc. VLDB Endow., 14(11):2190–2202, 2021. Cheu, A. and Nayak, D. Differentially private multi-sampling from distributions. In 36th International Conference on Algorithmic Learning Theory, 2025. URL https://openreview.net/forum? id=qbktUD8REC.
Limitations and future work: Our analysis is restricted to linear mixing-based DP mechanisms, requires public data from the same domain, and considers only histogram-based distribution estimators. Future work will extend domainaware privacy mechanisms to more complex distribution estimators, broadening the scope of P UB M IX’s applications.
Dockhorn, T., Cao, T., Vahdat, A., and Kreis, K. Differentially private diffusion models. Transactions on Machine Learning Research, 2023. ISSN 2835-8856.
Acknowledgements
Dwork, C. and Roth, A. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3–4):211–407, 2014.
This work was supported by the National Science Foundation under Grant No: CIF 2231707, CIF 2312667, 2506573, and a grant from the Center for Wireless Intelligence at Georgia Tech. We also acknowledge support from Coefficient Giving and JPMorgan Chase. F.P. Calmon is also affiliated with Google Research as a Visiting Faculty Researcher.
Dwork, C., McSherry, F., Nissim, K., and Smith, A. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography, pp. 265–284, 2006. Flemings, J., Razaviyayn, M., and Annavaram, M. Differentially private next-token prediction of large language models. In Duh, K., Gomez, H., and Bethard, S. (eds.), Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pp. 4390–4404, June 2024.
Impact Statement This work advances DP synthetic generation by proposing public-data-aware privacy mechanisms. This method incorporates auxiliary public data directly into the privacycritical sampling step, improving utility while maintaining DP guarantees. By enabling the generation of higher-fidelity synthetic data under a given privacy budget, the proposed approach increases the practicality of privacy-preserving data sharing in domains where data access is limited (e.g., healthcare, finance and user-generated content). At the same time, synthetic data can be misused or misinterpreted. First, since DP protections depend on correct choice and reporting of privacy parameters, loose privacy budgets can undermine protections. Second, synthetic data may still encode and amplify social biases present in the private dataset. Finally, because our method leverages public data, careful governance is needed to ensure the public source is legitimately shareable and properly licensed.
Frigerio, L., Oliveira, A., Gomez, L., and Duverger, P. Differentially private generative adversarial networks for time series, continuous, and discrete open data. In ICT Systems Security and Privacy Protection, pp. 151–164, 2019. Fuentes, M., Mullins, B. C., McKenna, R., Miklau, G., and Sheldon, D. Joint selection: Adaptively incorporating public information for private synthetic data. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pp. 2404–2412, 2024. Gallager, R. G. Information Theory and Reliable Communication. John Wiley & Sons, Inc., USA, 1968. ISBN 0471290483.
References Abacha, F., Teo, S., Cordeiro, L., and Mustafa, M. Synthetic data aided federated learning using foundation models. In Federated Learning in the Age of Foundation Models FL 2024 International Workshops, pp. 106–118, 2025.
Ghalebikesabi, S., Berrada, L., Gowal, S., Ktena, I., Stanforth, R., Hayes, J., De, S., Smith, S. L., Wiles, O., and Balle, B. Differentially private diffusion models generate useful synthetic images. availabe at: arXiv:2302.13861, 2023.
Amin, K., Bie, A., Kong, W., Kurakin, A., Ponomareva, N., Syed, U., Terzis, A., and Vassilvitskii, S. Private prediction for large-scale synthetic text generation. In Al-Onaizan, Y., Bansal, M., and Chen, Y.-N. (eds.), Findings of the Association for Computational Linguistics: EMNLP 2024, November 2024.
Ginart, A. A., van der Maaten, L., Zou, J., and Guo, C. Submix: Practical private prediction for large-scale language models. availabe at: arXiv:2201.00971, 2022. Hardt, M., Ligett, K., and Mcsherry, F. A simple and practical algorithm for differentially private data release. In Advances in Neural Information Processing Systems, 2012.
Cai, K., Lei, X., Wei, J., and Xiao, X. Data synthesis via 10
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
Hay, M., Rastogi, V., Miklau, G., and Suciu, D. Boosting the accuracy of differentially private histograms through consistency. Proc. VLDB Endow., 3(1–2):1021–1032, 2010.
Papernot, N., Song, S., Mironov, I., Raghunathan, A., Talwar, K., and Úlfar Erlingsson. Scalable private learning with PATE. arXiv:1802.08908, 2018. Pfitzner, B. and Arnrich, B. DPD-fVAE: Synthetic data generation using federated variational autoencoders with differentially-private decoder. availabe at: arXiv:2211.11591, 2022.
Hou, C., Wang, M.-Y., Zhu, Y., Lazar, D., and Fanti, G. Private federated learning using preference-optimized synthetic data. In Forty-second International Conference on Machine Learning, 2025.
Ponomareva, N., Xu, Z., McMahan, H. B., Kairouz, P., Rosenblatt, L., Cohen-Addad, V., Guzmán, C., McKenna, R., Andrew, G., Bie, A., Yu, D., Kurakin, A., Zadimoghaddam, M., Vassilvitskii, S., and Terzis, A. How to dp-fy your data: A practical guide to generating synthetic data with differential privacy. arXiv preprint arXiv:2512.03238, 2025.
Li, J., Shang, J., and McAuley, J. UCTopic: Unsupervised contrastive learning for phrase representations and topic mining. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 6159–6169, May 2022. Lin, Z., Gopi, S., Kulkarni, J., Nori, H., and Yekhanin, S. Differentially private synthetic data via foundation model APIS 1: Images. In ICLR, 2024.
Qardaji, W., Yang, W., and Li, N. Understanding hierarchical methods for differentially private histograms. Proc. VLDB Endow., 6(14):1954–1965, 2013.
Liu, T., Vietri, G., Steinke, T., Ullman, J., and Wu, S. Leveraging public data for practical private query release. In Proceedings of the 38th International Conference on Machine Learning, pp. 6968–6977, 2021a.
Reimers, N. and Gurevych, I. Sentence-BERT: Sentence embeddings using siamese BERT-networks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, 11 2019. URL http://arxiv. org/abs/1908.10084.
Liu, T., Vietri, G., and Wu, S. Z. Iterative methods for private synthetic data: Unifying framework and new methods. Advances in Neural Information Processing Systems, 34:690–702, 2021b.
Sason, I. and Verdú, S. f -divergence inequalities. IEEE Transactions on Information Theory, 62(11):5973–6006, 2016.
Liu, T., Tang, J., Vietri, G., and Wu, S. Generating private synthetic data with genetic algorithms. In International Conference on Machine Learning, pp. 22009– 22027. PMLR, 2023.
Slavkovic, J. S. A. and Reimherr, M. Private posterior inference consistent with public information: A case study in small area estimation from synthetic census data. In Privacy in Statistical Databases, pp. 323–336, 2020.
Liu, Y., Ott, M., Goyal, N., Du, J., Joshi, M., Chen, D., Levy, O., Lewis, M., Zettlemoyer, L., and Stoyanov, V. Roberta: A robustly optimized BERT pretraining approach. CoRR, abs/1907.11692, 2019. URL http://arxiv.org/ abs/1907.11692.
Tang, X., Shin, R., Inan, H. A., Manoel, A., Mireshghallah, F., Lin, Z., Gopi, S., Kulkarni, J., and Sim, R. Privacypreserving in-context learning with differentially private few-shot generation. In The Twelfth International Conference on Learning Representations, 2024. URL https: //openreview.net/forum?id=oZtt0pRnOl.
Long, Y., Wang, B., Yang, Z., Kailkhura, B., Zhang, A., Gunter, C., and Li, B. G-PATE: Scalable differentially private data generator via private aggregation of teacher discriminators. In NeurIPS, pp. 2965–2977, 2021.
Touvron, H., Martin, L., Stone, K., Albert, P., Almahairi, A., Babaei, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., et al. Llama 2: Open foundation and finetuned chat models. arXiv preprint arXiv:2307.09288, 2023.
McKenna, R., Sheldon, D., and Miklau, G. Graphical-model based estimation and inference for differential privacy. In ICML, 2019. McKenna, R., Miklau, G., and Sheldon, D. Winning the NIST contest: A scalable and general approach to differentially private synthetic data. J. Priv. Confidentiality, 11 (3), 2021.
Tran, T., Backurs, A., Lin, Z., Reis, V., Xiong, L., and Yekhanin, S. Differentially private synthetic data via APIs 4: Tabular data, 2026. URL https://openreview. net/forum?id=SPgqHr2jiK.
McKenna, R., Mullins, B., Sheldon, D., and Miklau, G. AIM: an adaptive and iterative mechanism for differentially private synthetic data. Proc. VLDB Endow., 15(11): 2599–2612, July 2022.
U.S. Census Bureau. ACS PUMS data dictionary. https: //www2.census.gov/programs-surveys/ acs/tech_docs/pums/data_dict/PUMS_ 11
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
Data_Dictionary_2024.pdf, 2024. 2026-01-29.
Accessed:
Vidulin, V., Lustrek, M., Kaluza, B., Pitlaver, R., and Krivec, J. Localization data for person activity. UCI Machine Learning Repository, 2010. URL https: //archive.ics.uci.edu/dataset/201/ localization+data+for+person+activity. Accessed: July 21, 2026. Wang, H., Sudalairaj, S., Henning, J., Greenewald, K., and Srivastava, A. Post-processing private synthetic data for improving utility on selected measures. In Proceedings of the 37th International Conference on Neural Information Processing Systems, 2023. Xie, C., Lin, Z., Backurs, A., Gopi, S., Yu, D., Inan, H., Nori, H., Jiang, H., Zhang, H., Lee, Y. T., Li, B., and Yekhanin, S. Differentially private synthetic data via foundation model APIs 2: Text. In ICML, 2024. Yan, A., He, Z., Li, J., Zhang, T., and McAuley, J. Personalized showcases: Generating multi-modal explanations for recommendations. In Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 2251–2255, 2023. Yelp Inc. Yelp open dataset. https://www.yelp. com/dataset, 2023. Accessed: July 21, 2026. Yue, X., Inan, H., Li, X., Kumar, G., McAnallen, J., Sun, H., Levitan, D., and Sim, R. Synthetic text generation with differential privacy: A simple and practical recipe. In ACL 2023, 2023. Zhang, J., Cormode, G., Procopiuc, C. M., Srivastava, D., and Xiao, X. Privbayes: Private data release via bayesian networks. ACM Trans. Database Syst., 42(4), 2017. Zhang, J., Liu, Y., FU, J., Hua, Y., Zou, T., Cao, J., and Yang, Q. PCEvolve: Private contrastive evolution for synthetic dataset generation via few-shot private data and generative APIs. In Forty-second International Conference on Machine Learning, 2025. URL https: //openreview.net/forum?id=IKCfxWtTsu. Zhang, Z., Wang, T., Li, N., Honorio, J., Backes, M., He, S., Chen, J., and Zhang, Y. PrivSyn: Differentially private data synthesis. In 30th USENIX Security Symposium (USENIX Security 21), pp. 929–946, August 2021. ISBN 978-1-939133-24-3.
12
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
A. Additional Details on Related Work On methods using linear mixing: Certain private prediction variants (Flemings et al., 2024; Ginart et al., 2022) are alternatives to DP training methods such as DP stochastic gradient descent (DP-SGD), where instead of privatizing the model itself, privacy is enforced at inference time by perturbing the model’s output. In the LLM setting, this typically involves mixing or projecting the private model’s next-token distribution toward a public distribution to limit leakage from memorized private data. While both PubMix and private prediction variants involve linear mixing and public distributions, they differ fundamentally in goal and technical design. • Goal: Private prediction protects the privacy of an LLM’s fine-tuning data at inference time, one token prediction at a time. In contrast, PUBMIX introduces domain-aware, sample-aware synthetic data generation from histograms, with the goal of producing m privacy-protected samples whose distribution is as close as possible to the private data distribution. • Optimization: Private prediction methods (Flemings et al., 2024; Ginart et al., 2022) linearly mix private token distributions with a fixed public distribution and optimize only the mixing coefficient to remain as close as possible to the private distribution while satisfying privacy. PUBMIX instead mixes a private normalized histogram with a noise distribution and jointly optimizes both the mixing weight β and the noise distribution Pnse to minimize the distance to the private distribution. In this sense, PubMix generalizes the optimization step of private prediction by introducing an additional optimization variable, which provides extra flexibility to improve the utility of the mixing step. • Role of public data: In private prediction, the public distribution mainly serves as a source of noise. In PUBMIX, public data is used more structurally: it informs the design of a domain-aware noise distribution. In other words, using the public distribution as the noise distribution is only a special case of PUBMIX. Generally, the optimal noise distribution drifts toward a floor-raised version of the public distribution. This distinction matters especially when the public distribution is sparse (which is common in token distributions), since fixing it directly can force the mixed distribution to be much closer to the public distribution than to the private ones, which degrades utility. PUBMIX avoids this by jointly optimizing the noise distribution and mixing parameter. While these differences exist between PUBMIX and private prediction methods, the extension of PUBMIX to general discrete distributions beyond histograms (briefly discussed in App. H) can be applied on token distributions. In that sense, PUBMIX can potentially serve as a drop-in privacy module for the linear mixing step in private prediction, provided it is paired with an appropriate privacy accounting across generated tokens.
B. Proofs of Section 3 Lemma B.1. Let A = (A1 , . . . , Ad ) be a probability mass function (PMF) on a finite set Ω = {ω1 , . . . , ωd }, and let U = (U1 , . . . , Ud ) denote the uniform distribution on Ω, i.e., Ui = 1/d for all i. For any threshold t ∈ [0, 1/d], let B = WF(A, t) denote the t-water-filled version of A as in Definition 4.3. Then, the total variation distance to the uniform distribution does not increase under water-filling, i.e., ∥B − U ∥TV ≤ ∥A − U ∥TV . Proof. Let A = (A1 , . . . , Ad ) be the original PMF, B = (B1 , . . . , Bd ) the water-filled PMF, and U = (U1 , . . . , Ud ) the uniform distribution with Ui = 1/d. We also denote by Q = (Q1 , . . . , Qd ) an arbitrary PMF for intermediate arguments. For any PMF Q on Ω, the total variation distance to the uniform distribution U satisfies )︃ d ∑︂ (︃ 1 ∑︂ 1 1 ∥Q − U ∥TV = |Qi − | = Qi − . (16) 2 i=1 d d 1 i: Qi > d
Therefore, it suffices to show that ∑︂ (︃ 1 i:Bi > d
Bi −
1 d
)︃
∑︂ (︃
≤
1 i:Ai > d
Ai −
1 d
)︃ .
(17)
∑︁d Recall that Bi = max{t, Ai − τ }, where τ is chosen such that i=1 Bi = 1. We first show that τ ≥ 0. Suppose, for the sake of contradiction, that τ < 0. Then Ai − τ > Ai for all i, which implies Bi ≥ Ai − τ > Ai for all i. Consequently, ∑︁d ∑︁d ∑︁d i=1 Bi > i=1 Ai = 1, which contradicts the normalization condition i=1 Bi > 1. Hence, τ ≥ 0. 13
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
Consider any index i such that Ai ≤ d1 . Since t ≤ d1 and τ ≥ 0, we have Bi = max{t, Ai − τ } ≤
1 . d
(18)
Hence, no coordinate whose original mass is at most 1/d can exceed 1/d after water-filling. Consider any index i such that Ai > d1 . As Ai > t and τ ≥ 0, Bi = Ai − τ ≤ Ai .
(19)
Hence, any excess mass above 1/d is weakly reduced by the water-filling operation. Combining the above observations, the set {i : Bi > d1 } is a subset of {i : Ai > d1 }, and for each such index, Bi − d1 ≤ Ai − d1 . Summing over all indices yields ∥B − U ∥TV ≤ ∥A − U ∥TV ,
(20)
which completes the proof.
C. Proof of Theorem 4.1 In this section, we provide the proof of Theorem 4.1. First, we restate Theorem 4.1, and then provide the proof in the following order. • Rewrite the privacy constraint in (2) in terms of the privacy parameters ε, δ, required samples m, noise distribution ′ ′ Pnse , mixing coefficient β, and a = Psyn (i), b = Psyn (j), where i and j are the two distinct indices at which the ′ ′ normalized histograms, P̄prv and P̄prv , of neighboring datasets Dprv and Dprv differ. Specifically, we show that the privacy constraint simplifies to: sup Eeε (P ⊗m ∥Q⊗m ) ≤ δ
(21)
a,b
[︂ ]︂ 1−β where P and Q are distributions given by P = a + 1−β and Q = [a, b, 1 − a − b], and , b − , 1 − a − b n n Eeε (·∥·) is the Eγ divergence. • We show that supa,b Eeε (P ⊗m ∥Q⊗m ) is non-increasing in a and b for any given ε, δ, m, n, β, Pnse , and characterize the exact supa,b Eeε (P ⊗m ∥Q⊗m ), which leads to Theorem 4.1. Theorem 4.1 restated:[Feasible mixing weights β] Fix ε > 0, δ ∈ (0, 1), private dataset size n, and the required number of synthetic samples m ≥ 1. Let Pnse ∈ ∆d be any noise distribution and define Nmin1 and Nmin2 to be the two smallest elements of Pnse with Nmin1 ≤ Nmin2 . Then, for every β ≥ βmin (Nmin1 , Nmin2 ), the m synthetic samples drawn from Psyn in (1) satisfy the DP constraint in (2), where βmin (Nmin1 , Nmin2 ) is given by the solution to β in: max{h1 (β, ε, n, m, Nmin1 , Nmin2 ), h2 (β, ε, n, m, Nmin1 , Nmin2 )} = δ
(22)
where h1 (β, ε, n, m, Nmin1 , Nmin2 ) =
∑︂ λ,µ≥0 λ+µ≤m
[︄(︃
m! λ!µ!(m − λ − µ)!
1−β βNmin1 + n
(︃ )︃m−λ−µ 1−β 1 − β(Nmin1 + Nmin2 ) − n
)︃λ
µ
(βNmin2 ) − e
ε
(︃
1−β βNmin2 + n
)︃µ
]︄ λ
(βNmin1 )
(23) +
where [x]+ = max{x, 0}, and h2 (β, ε, n, m, Nmin1 , Nmin2 ) is the same as h1 (β, ε, n, m, Nmin1 , Nmin2 ) with Nmin1 and Nmin2 swapped. Moreover, βmin (Nmin1 , Nmin2 ) is decreasing in Nmin1 and Nmin2 . 14
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
Lemma C.1. For any fixed privacy parameters ε > 0 and δ ∈ (0, 1), required number of synthetic samples m, and any fixed noise distribution Pnse ∈ ∆d , the privacy constraint in (2) is simplified to: Eeε (P ⊗m ∥Q⊗m ) =
sup (a,b)∈F (β,Pnse )
sup
f (a, b, ε, β) ≤ δ
(24)
(a,b)∈F (β,Pnse )
where Eeε (P ⊗m ∥Q⊗m ) denotes the hockey-stick divergence (E distributions P ⊗m and [︂ γ divergence) between the product ]︂
1−β Q⊗m with P and Q denoting the three-point distributions P = a + 1−β n , b − n , 1 − a − b and Q = [a, b, 1 − a − b].
F(β, Pnse ) is the feasible set of (a, b), and, f (a, b, ε, β) =
∑︂ λ,µ≥0 λ+µ≤m
m! (1 − a − b)m−λ−µ λ!µ!(m − λ − µ)!
[︄(︃
1−β a+ n
]︄ )︃λ (︃ )︃µ 1−β ε λ µ b− −e a b ≤δ n
(25)
+
′ ′ Proof: Consider the privacy constraint in (2): P(Dsyn ∈ S) ≤ eε P(Dsyn ∈ S) + δ, ∀S ⊆ X m , ∀Dprv , Dprv , which is equivalent to: ′ max P(Dsyn ∈ S) − eε P(Dsyn ∈ S) ≤ δ,
S⊆X m
′ ∀Dprv , Dprv
(26)
Let Y = {y1 , . . . , ym } ∈ X m denote any generic candidate set of synthetic samples. Then, we can write the privacy constraint in (26) as: [︄ m ]︄ m ∑︂ ∏︂ ∏︂ ε ′ ′ Psyn (yk ) − e Psyn (yk ) ≤ δ, ∀Dprv , Dprv (27) Y∈X m
k=1
k=1
+
where [x]+ = max{x, 0}. From the construction of Psyn in (1), we have, Psyn (y) = (1 − β)P̄prv (y) + βPnse (y)
(28)
′ ′ Psyn (y) = (1 − β)P̄prv (y) + βPnse (y)
(29)
⎧ 1 ′ ⎪ ⎨P̄prv (y) + n , y = i ′ P̄prv (y) = P̄prv (y) − n1 , y = j ⎪ ⎩ ′ y ̸= i, j P̄prv (y),
(30)
for any y ∈ X where,
′ for some i, j ∈ X . Since each yk is sampled i.i.d. from Psyn (or Psyn ), (27) can be written in terms of the Eγ divergence ⊗m ′⊗m between the product distributions Psyn and Psyn . ⊗m ′⊗m Eeε (Psyn ∥Psyn ) ≤ δ,
′ ∀Dprv , Dprv
For product distributions, the likelihood ratio of any realization Y = (y1 , . . . , ym ) is P
(31) Psyn (yk ) ′ k=1 Psyn (yk ) , which depends only on
∏︁m
(y)
⊗m ′⊗m the number of times i and j appear among the m samples, since Psyn = 1 for all y ∈ / {i, j}. Therefore, Eeε (Psyn ∥Psyn ) ′ syn (y) ′ depends on Psyn and Psyn only through the probabilities assigned to i, j, and the total remaining mass. With the notation 1−β ′ ′ Psyn (i) = a, Psyn (j) = b, Psyn (i) = a + 1−β n and Psyn (j) = b − n , we can equivalently write (31) as: ′ Eeε (P ⊗m ∥Q⊗m ) ≤ δ, ∀Dprv , Dprv (32) [︂ ]︂ 1−β where P and Q are three-point distributions given by P = a + 1−β n , b − n , 1 − a − b and Q = [a, b, 1 − a − b], ′ corresponding to the probabilities of outcomes i, j, and the aggregate remainder in Psyn and Psyn , respectively. Moreover, ′ we can replace the ∀Dprv , Dprv term in (32) by the supremum over (a, b) for any given β and Pnse . This gives the following equivalent form of the privacy constraint in (32):
sup
Eeε (P ⊗m ∥Q⊗m ) ≤ δ
(a,b)∈F (β,Pnse )
15
(33)
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
The numbers of samples “i”, “j”, or “anything other than i, j” (sampled i.i.d.) follow a multinomial distribution with 1−β ⊗m probabilities (a + 1−β and Q⊗m . This simplifies the n , b − n , 1 − a − b) and (a, b, 1 − a − b), respectively, for P privacy constraint in (33) to: [︄(︃ ]︄ )︃λ (︃ )︃µ ∑︂ m! 1 − β 1 − β − eε aλ bµ ≤ δ (34) sup (1 − a − b)m−λ−µ a+ b− λ!µ!(m − λ − µ)! n n (a,b)∈F (β,Pnse ) λ,µ≥0 λ+µ≤m
+
This completes the proof of Lemma C.1. ■ Lemma C.2. For any fixed Pnse ∈ ∆d and β ∈ [0, 1], Eeε (P ⊗m ∥Q⊗m ) is non-increasing in a and b. Proof: First, we[︂ show that Eeε (P ⊗m ∥Q⊗m]︂) is non-increasing in a for any fixed b. For this, de1−β 1−β fine Pa = a + n , b − n , 1 − a − b and Qa = [a, b, 1 − a − b], and similarly Pa+∆ = [︂ ]︂ 1−β 1−β a + ∆ + n , b − n , 1 − a − ∆ − b and Qa+∆ = [a + ∆, b, 1 − a − ∆ − b] for some small ∆ > 0. Consider the following stochastic channel T , applied independently to each sample y, sampled from Pa and Qa : ⎧ 1, y ′ = y, y ∈ {i, j}, ⎪ ⎪ ⎪ ⎨ ∆ y ′ = i, y = “other”, T (y ′ | y) = 1 − a − b , ⎪ ⎪ ∆ ⎪ ⎩1 − , y ′ = “other”, y = “other”. 1−a−b
(35)
where “other” denotes the combined event of all y ̸= i, j. The output distributions T Pa and T Qa are given by: 1−β + ∆, n 1−β (T Pa )(j) = b − , n (T Pa )(“other”) = 1 − a − b − ∆, (T Pa )(i) = a +
(36) (37) (38)
and (T Qa )(i) = a + ∆,
(39)
(T Qa )(j) = b,
(40)
(T Qa )(“other”) = 1 − a − b − ∆.
(41)
These match Pa+∆ and Qa+∆ , respectively: T Pa = Pa+∆
and
T Qa = Qa+∆ .
(42)
Since the channel T is applied to all m samples independently and identically, we have ⊗m T ⊗m : Pa⊗m ↦→ Pa+∆
and
T ⊗m : Q⊗m ↦→ Q⊗m a a+∆ .
(43)
By the data processing inequality for the hockey-stick divergence (Sason & Verdú, 2016), which states that Eγ (T P ∥T Q) ≤ Eγ (P ∥Q) for any stochastic channel T , we conclude that ⊗m ⊗m Eeε (Pa+∆ ∥Q⊗m ∥Q⊗m a ). a+∆ ) ≤ Eeε (Pa
(44)
This establishes that Eeε (P ⊗m ∥Q⊗m ) is non-increasing in a. An analogous argument, with the channel T modified to move mass from outcome “other” to outcome j instead of outcome i, shows that Eeε (P ⊗m ∥Q⊗m ) is also non-increasing in b. ■ 16
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
From Lemma C.2, for fixed ε, Pnse , and β, the maximum Eeε (P ⊗m ∥Q⊗m ) is achieved at the smallest values of a and b, ′ ′ denoted by amin and bmin . Recall that a = Psyn (i) and b = Psyn (j) where, ′ ′ Psyn (y) = (1 − β)P̄prv (y) + βPnse (y),
∀y ∈ X
(45)
Thus, the smallest a and b for fixed β and Pnse are given by, amin = βNmin1 1−β + βNmin2 bmin = n
(46)
a′min = βNmin2 1−β b′min = + βNmin1 n
(48)
(47)
or in the reverse order:
(49)
where Nmin1 and Nmin2 are the two smallest elements of Pnse . This simplifies the privacy constraint in Lemma C.1 to: max{f (amin , bmin , ε, β), f (a′min , b′min , ε, β)} ≤ δ
(50)
Thus, for given ε, δ, m and Pnse , the optimum mixing parameter is given by, βmin (Pnse ) = inf {β ∈ [0, 1] : max{f (amin , bmin , ε, β), f (a′min , b′min , ε, β)} ≤ δ}
(51)
where we have ignored the dependency of β on ε, δ and m since they are fixed for a given setting, and Pnse is the only variable that is yet to be optimized. Note that βmin (Pnse ) depends on Pnse only though its two smallest elements. Thus, for a given Pnse , the minimum mixing coefficient is given by: βmin (Nmin1 , Nmin2 ) = inf {β ∈ [0, 1] : max{f (amin , bmin , ε, β), f (a′min , b′min , ε, β)} ≤ δ}
(52)
where f (amin , bmin , ε, β) =
∑︂ λ,µ≥0 λ+µ≤m
[︄(︃
m! λ!µ!(m − λ − µ)!
1−β βNmin1 + n
)︃λ
(︃ 1 − β(Nmin1 + Nmin2 ) −
1−β n
)︃m−λ−µ
]︄ (︃ )︃µ 1−β λ (βNmin2 ) − e βNmin2 + (βNmin1 ) n µ
ε
(53) +
and f (a′min , b′min , ε, β) =
∑︂ λ,µ≥0 λ+µ≤m
[︄(︃
m! λ!µ!(m − λ − µ)!
1−β βNmin2 + n
(︃ 1 − β(Nmin1 + Nmin2 ) −
)︃λ
µ
(βNmin1 ) − e
ε
(︃
1−β n
)︃m−λ−µ
1−β βNmin1 + n
]︄
)︃µ (βNmin2 )
λ
(54) +
Next, we show that f (amin , bmin , ε, β) and f (a′min , b′min , ε, β) are decreasing in β. Thus, for any Pnse with a fixed Nmin1 and Nmin2 , any β ≥ β(Nmin1 , Nmin2 ) satisfies the privacy constraint in (2). Lemma C.3. For any fixed Nmin1 , Nmin2 and ε > 0, max{f (amin , bmin , ε, β), f (a′min , b′min , ε, β)} is decreasing in β. Proof: From the monotonicity of Eeε (P ⊗m ∥Q⊗m ) in a and b established in the proof of Lemma C.2, for any fixed β, ε, Nmin1 and Nmin2 , we have the privacy constraint in (2) simplified to: ⊗m ′⊗m sup Eeε (Psyn ∥Psyn )=
′ Dprv ,Dprv
sup
⊗m ⊗m Eeε (P ⊗m ∥Q⊗m ) = max{Eeε (P∗⊗m ∥Q⊗m ∗ ), Eeε (P# ∥Q# )} ≤ δ
(a,b)∈F (β,Nmin1 ,Nmin2 )
(55) 17
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
where [︃ ]︃ 1−β 1−β P∗ = amin + , bmin − , 1 − amin − bmin n n
(56)
Q∗ = [amin , bmin , 1 − amin − bmin ]
(57)
[︃ ]︃ 1−β ′ 1−β ′ ′ ′ P# = amin + , bmin − , 1 − amin − bmin n n
(58)
Q# = [a′min , b′min , 1 − a′min − b′min ]
(59)
and
1−β ′ ′ with amin = βNmin1 , bmin = 1−β n + βNmin2 and amin = βNmin2 and bmin = n + βNmin1 . Note that ⊗m ⊗m ⊗m ⊗m ′ ′ ε ε f (amin , bmin , ε, β) = Ee (P∗ ∥Q∗ ) and f (amin , bmin , ε, β) = Ee (P# ∥Q# ). Moreover, amin , a′min , bmin , b′min are functions of β. Suppose for a given Nmin1 , Nmin2 , β0 satisfies:6
max{f (amin (β0 ), bmin (β0 ), ε, β0 ), f (a′min (β0 ), b′min (β0 ), ε, β0 )} ≤ δ
(60)
In other words, the privacy constraint holds for all neighboring datasets at β = β0 . For any β > β0 , we can write: Psyn,β = (1 − β)P̄prv + βPnse (︃ )︃ ]︁ 1 − β [︁ 1−β = (1 − β0 )P̄prv + β0 Pnse + 1 − Pnse 1 − β0 1 − β0 = α Psyn,β0 + (1 − α) Pnse
(61)
1−β ∈ [0, 1] and Psyn,β0 = (1 − β0 )P̄prv + β0 Pnse . Similarly, for any neighboring dataset: where α = 1−β 0 ′ ′ Psyn,β = α Psyn,β + (1 − α) Pnse . 0
(62)
′ ′ That is, both Psyn,β and Psyn,β are obtained by applying the same stochastic channel T to Psyn,β0 and Psyn,β , respectively, 0
where T takes the synthetic distribution as input and outputs a sample from the synthetic distribution with mixing parameter β0 with probability α and a sample from Pnse with probability 1 − α. Since T is applied independently to each of the m samples, by the data processing inequality for the hockey-stick divergence: ⊗m ′⊗m ⊗m ′⊗m Eeε (Psyn,β ∥Psyn,β ) ≤ Eeε (Psyn,β ∥Psyn,β ) 0 0
(63)
′ Since (63) holds for every neighboring pair (Dprv , Dprv ), and the channel T does not depend on the choice of neighboring pair, we can take the supremum over all neighboring pairs on both sides:
sup ′ Dprv ,Dprv
⊗m ′⊗m Eeε (Psyn,β ∥Psyn,β )≤
sup ′ Dprv ,Dprv
⊗m ′⊗m Eeε (Psyn,β ∥Psyn,β ) ≤ δ. 0 0
(64)
where the last inequality follows from the fact that privacy is guaranteed at β = β0 . From the monotonicity of Eeε (P ⊗m ∥Q⊗m ) in a and b established in (44), the supremum over all neighboring pairs at any fixed β is achieved at (amin , bmin ) or (a′min , b′min ) for a given Pnse . Therefore, max{f (amin (β), bmin (β), ε, β), f (a′min (β), b′min (β), ε, β)} ≤ max{f (amin (β0 ), bmin (β0 ), ε, β0 ), f (a′min (β0 ), b′min (β0 ), ε, β0 )} ≤ δ,
(65)
establishing that max{f (amin , bmin , ε, β), f (a′min , b′min , ε, β)} is decreasing in β. ■ With Lemma C.3 and the characterization of βmin (Nmin1 , Nmin2 ) in (52), we claim that for any fixed Nmin1 , Nmin2 and ε, any β ≥ β(Nmin1 , Nmin2 ) satisfies the privacy constraint in (2). To simplify the process of computing βmin (Nmin1 , Nmin2 ) for given Nmin1 , Nmin2 from (52), we next show that max{f (amin (β), bmin (β), ε, β), f (a′min (β), b′min (β), ε, β)} is continuous in β (see Lemma C.4). Then, together with the fact that max{f (amin (β), bmin (β), ε, β), f (a′min (β), b′min (β), ε, β)} is decreasing in β (Lemma C.3), we find βmin (Nmin1 , Nmin2 ) for any given Nmin1 , Nmin2 by solving: max{f (amin (β), bmin (β), ε, β), f (a′min (β), b′min (β), ε, β)} = δ
(66)
Since amin , a′min , bmin , b′min are functions of β, we make it explicit by writing f (amin , bmin , ε, β) = f (amin (β), bmin (β), ε, β) and f (a′min , b′min , ε, β) = f (a′min (β), b′min (β), ε, β). 6
18
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
Lemma C.4. For any fixed Nmin1 , Nmin2 and ε, max{f (amin (β), bmin (β), ε, β), f (a′min (β), b′min (β), ε, β)} is continuous in β. Proof: Consider: f (amin (β), bmin (β), ε, β) =
∑︂ λ,µ≥0 λ+µ≤m
[︄(︃
m! λ!µ!(m − λ − µ)!
1−β βNmin1 + n
(︃ )︃m−λ−µ 1−β 1 − β(Nmin1 + Nmin2 ) − n
)︃λ
]︄ (︃ )︃µ 1−β λ (βNmin2 ) − e βNmin2 + (βNmin1 ) n µ
ε
Each term in the summation is indexed by a fixed (λ, µ) with λ, µ ≥ 0 and λ + µ ≤ m, and takes the form [︁ ]︁ m! gλ,µ (β) = c(β)m−λ−µ r1 (β)λ q2 (β)µ − eε r2 (β)µ q1 (β)λ + λ!µ!(m − λ − µ)!
(67) +
(68)
1−β where c(β) = 1 − β(Nmin1 + Nmin2 ) − 1−β n , qi (β) = βNmini , and ri (β) = βNmini + n . Each of c(β), qi (β), and ri (β) is continuous in β on [0, 1], and therefore h(β) ≜ r1 (β)λ q2 (β)µ − eε r2 (β)µ q1 (β)λ is also continuous in β. Since the function x ↦→ [x]+ = max{0, x} is continuous, the composition [h(β)]+ is continuous. It follows that each gλ,µ (β) is a product of continuous functions and hence continuous. Since the summation is over a finite set of (λ, µ) pairs that does not depend on β, the function ∑︂ f (amin (β), bmin (β), ε, β) = gλ,µ (β) (69) λ,µ≥0 λ+µ≤m
is a finite sum of continuous functions, and is therefore continuous in β. Similarly, f (a′min (β), b′min (β), ε, β) is also continuous in β. Thus, the maximum of the two functions is also continuous in β. ■ Lemma C.5. βmin (Nmin1 , Nmin2 ) as defined in (52) is non-increasing in both Nmin1 and Nmin2 . Proof: Recall the two worst-case pairs: (︂ )︂ (amin , bmin ) = βNmin1 , 1−β n + βNmin2 , (︂ )︂ (a′min , b′min ) = βNmin2 , 1−β + βN . min 1 n
(70) (71)
All amin , bmin , a′min , b′min are linear and non-decreasing in Nmin1 and Nmin2 as β ∈ [0, 1]. Since f (a, b, ε, β) is nonincreasing in a and b (Lemma C.2), it follows that for any fixed β, f (amin , bmin , ε, β) and f (a′min , b′min , ε, β) are each non-increasing in Nmin1 and Nmin2 . Therefore their maximum, g(β, Nmin1 , Nmin2 ) := max {f (amin , bmin , ε, β), f (a′min , b′min , ε, β)} ,
(72)
is also non-increasing in Nmin1 and Nmin2 for any fixed β. ′ Now fix any Nmin1 ≤ Nmin (the argument for Nmin2 is identical). Let β ∗ = βmin (Nmin1 , Nmin2 ) in (52), so that by 1 definition:
g(β ∗ , Nmin1 , Nmin2 ) ≤ δ.
(73)
′ g(β ∗ , Nmin , Nmin2 ) ≤ g(β ∗ , Nmin1 , Nmin2 ) ≤ δ, 1
(74)
Since g is non-increasing in Nmin1 : ∗
Therefore, β is in the feasible range in (52): ′ β ∗ ∈ {β ∈ [0, 1] : g(β, Nmin , Nmin2 ) ≤ δ} 1
(75)
′ Since βmin (Nmin , Nmin2 ) is the infimum over all feasible β: 1 ′ βmin (Nmin , Nmin2 ) ≤ β ∗ = βmin (Nmin1 , Nmin2 ). 1
Hence βmin (Nmin1 , Nmin2 ) is non-increasing in Nmin1 , and by the same argument, in Nmin2 . ■ This completes the proof of Theorem 4.1. 19
(76)
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
D. Details from Section 4 D.1. Proof of Asymptotic Optimality The optimization in (9) replaces βmin (Nmin1 , Nmin2 ) by the more conservative quantity βmin (Nmin1 , Nmin1 ). Since Nmin2 ≥ Nmin1 and βmin (Nmin1 , Nmin2 ) is non-increasing in its arguments (Lemma C.5), this yields an upper bound on the original objective. Moreover, the simplex constraint Nmin1 + (d − 1)Nmin2 ≤ 1 implies: 0 ≤ Nmin2 − Nmin1 ≤
1 . d−1
(77)
Lemma D.1. For any fixed Nmin1 ∈ [0, 1/d], βmin (Nmin1 , Nmin2 ) is continuous in Nmin2 . Consequently, sup |βmin (Nmin1 , Nmin2 ) − βmin (Nmin1 , Nmin1 )| → 0
as d → ∞.
(78)
Pnse ∈∆d
Moreover, the optimal value of the upper-bound problem in (9) converges to the optimal value of the original problem. Any optimizer of the upper-bound problem is therefore asymptotically optimal for the original problem. Proof. Assume that βmin (Nmin1 , Nmin2 ) is continuous in Nmin2 . The proof is provided at the end. Let N1 (Pnse ) := Nmin1 and N2 (Pnse ) := Nmin2 , where N1 (Pnse ) ≤ N2 (Pnse ) are the two smallest coordinates of Pnse . Define Ψ(Pnse ) :=
max
T V (P̄prv , Pnse ).
P̄prv ∈Bγ,P̄
(79)
pub
After optimizing over β, the objective in the left-hand side of (9) can be written as Fd (Pnse ) = βmin (N1 (Pnse ), N2 (Pnse ))Ψ(Pnse ),
(80)
while the upper-bound objective in the right-hand side of (9) is F˜︁d (Pnse ) = βmin (N1 (Pnse ), N1 (Pnse ))Ψ(Pnse ).
(81)
Since N2 (Pnse ) ≥ N1 (Pnse ), and since βmin is non-increasing in each of its arguments, we have βmin (N1 (Pnse ), N2 (Pnse )) ≤ βmin (N1 (Pnse ), N1 (Pnse )).
(82)
Therefore, Fd (Pnse ) ≤ F˜︁d (Pnse )
∀Pnse ∈ ∆d .
(83)
Thus, Vd :=
inf
Pnse ∈∆d
Fd (Pnse ) ≤
inf
Pnse ∈∆d
F˜︁d (Pnse ) =: V˜︁d ,
(84)
so the right-hand side of (9) is indeed an upper bound on the original objective. Next, we bound the gap between the two objectives. For any Pnse ∈ ∆d , 0 ≤ F˜︁d (Pnse ) − Fd (Pnse ) = [βmin (N1 (Pnse ), N1 (Pnse )) − βmin (N1 (Pnse ), N2 (Pnse ))] Ψ(Pnse ).
(85)
Since total variation distance is at most 1, we have 0 ≤ Ψ(Pnse ) ≤ 1.
(86)
0 ≤ F˜︁d (Pnse ) − Fd (Pnse ) ≤ βmin (N1 (Pnse ), N1 (Pnse )) − βmin (N1 (Pnse ), N2 (Pnse )).
(87)
Hence,
20
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
We now use the simplex constraint. Since Pnse ∈ ∆d , its coordinates sum to one. Because N1 and N2 are the smallest and second-smallest coordinates, all coordinates except the smallest one are at least N2 . Therefore, for any Pnse ∈ ∆d , 1=
d ∑︂
Pnse (i) ≥ N1 + (d − 1)N2 .
(88)
1 − N1 . d−1
(89)
i=1
Thus, N2 ≤ Since N2 ≥ N1 , we obtain 0 ≤ N2 − N1 ≤
1 − dN1 1 1 − N1 − N1 = ≤ . d−1 d−1 d−1
(90)
1 d−1
(91)
Therefore, 0 ≤ N2 − N1 ≤
Assume that βmin (z1 , z2 ) is uniformly continuous in its second argument over the feasible region Ad = {(z1 , z2 ) : 0 ≤ z1 ≤ z2 , z1 + (d − 1)z2 ≤ 1} .
(92)
Then, since |N2 (Pnse ) − N1 (Pnse )| ≤
1 , d−1
∀Pnse ∈ ∆d
(93)
we have sup |βmin (N1 (Pnse ), N2 (Pnse )) − βmin (N1 (Pnse ), N1 (Pnse ))| → 0
(94)
Pnse ∈∆d
as d → ∞. Consequently, ⃓ ⃓ ⃓ ⃓ sup ⃓F˜︁d (Pnse ) − Fd (Pnse )⃓ → 0.
(95)
Pnse ∈∆d
It remains to show convergence of the optimal values. Since Fd (Pnse ) ≤ F˜︁d (Pnse ) pointwise, we have Vd ≤ V˜︁d .
(96)
F˜︁d (Pnse ) ≤ F˜︁d (Pd⋆ ).
(97)
Let Pd⋆ ∈ arg minPnse ∈∆d Fd (Pnse ). Then V˜︁d =
inf
Pnse ∈∆d
Therefore, V˜︁d ≤ Fd (Pd⋆ ) +
⃓ ⃓ ⃓ ⃓ sup ⃓F˜︁d (Pnse ) − Fd (Pnse )⃓ .
(98)
⃓ ⃓ ⃓ ⃓ sup ⃓F˜︁d (Pnse ) − Fd (Pnse )⃓ .
(99)
Pnse ∈∆d
Since Fd (Pd⋆ ) = Vd , we get 0 ≤ V˜︁d − Vd ≤
Pnse ∈∆d
Taking d → ∞, the right-hand side converges to zero. Hence, V˜︁d − Vd → 0. 21
(100)
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
Thus, the upper-bound problem in (9) has the same asymptotic optimal value as the original problem. Moreover, if P˜︁d⋆ ∈ arg min F˜︁d (Pnse ),
(101)
Fd (P˜︁d⋆ ) ≤ F˜︁d (P˜︁d⋆ ) = V˜︁d .
(102)
0 ≤ Fd (P˜︁d⋆ ) − Vd ≤ V˜︁d − Vd → 0.
(103)
Pnse ∈∆d
then
Therefore,
Hence, any optimizer of the upper-bound problem is asymptotically optimal for the original problem. Now, the only remaining component of the proof is the continuity of βmin (Nmin1 , Nmin2 ) in Nmin2 . Continuity of βmin (Nmin1 , Nmin2 ) in Nmin2 . Fix ε > 0, δ ∈ (0, 1), the private dataset size n, the number of released samples m, and Nmin1 . For notational simplicity, write z1 := Nmin1 ,
z2 := Nmin2 .
(104)
Recall from Theorem 4.1 that βmin (z1 , z2 ) is defined as βmin (z1 , z2 ) = inf {β ∈ [0, 1] : G(β, z1 , z2 ) = δ} ,
(105)
G(β, z1 , z2 ) := max {h1 (β, ε, n, m, z1 , z2 ), h2 (β, ε, n, m, z1 , z2 )} .
(106)
where
Here h1 and h2 are the expressions from Theorem 4.1. We first observe that G is continuous in (β, z1 , z2 ). Indeed, h1 is a finite sum of terms of the form: h1 (β, ε, n, m, z1 , z2 ) =
∑︂
]︄ (︃ )︃m−λ−µ [︄(︃ )︃λ (︃ )︃µ m! 1−β 1−β 1−β µ ε λ 1−β(z1 + z2 ) − βz1 + (βz2 ) − e βz2 + (βz1 ) λ!µ!(m − λ − µ)! n n n
λ,µ≥0 λ+µ≤m
+
(107) Each factor inside the summation is continuous in (β, z1 , z2 ), and the map x ↦→ [x]+ = max{x, 0} is continuous. Therefore h1 is continuous. The same argument applies to h2 , and since the maximum of two continuous functions is continuous, G is continuous. Now fix z1 , and consider z2 ↦→ βmin (z1 , z2 ). Let (k)
z2
→ z2 .
(108)
We show that (k)
βmin (z1 , z2 ) → βmin (z1 , z2 ).
(109)
β ⋆ := βmin (z1 , z2 ).
(110)
G(β ⋆ , z1 , z2 ) = δ,
(111)
Let
Then, we have,
22
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
Claim D.2. For every η > 0, G(β ⋆ − η, z1 , z2 ) > δ,
G(β ⋆ + η, z1 , z2 ) < δ.
(112)
Equivalently, the privacy curve crosses the level δ at β ⋆ , rather than remaining flat at δ. The proof of Claim D.2 is given at the end. Using Claim D.2, we prove upper and lower semicontinuity. First, fix any η > 0. By Claim D.2, G(β ⋆ + η, z1 , z2 ) < δ.
(113)
Since G is continuous in z2 , for all sufficiently large k, (k)
G(β ⋆ + η, z1 , z2 ) < δ.
(114)
(k)
(115)
Therefore, βmin (z1 , z2 ) ≤ β ⋆ + η for all sufficiently large k. Taking the limsup gives (k)
lim sup βmin (z1 , z2 ) ≤ β ⋆ + η.
(116)
k→∞
Since η > 0 was arbitrary, (k)
lim sup βmin (z1 , z2 ) ≤ β ⋆ .
(117)
G(β ⋆ − η, z1 , z2 ) > δ.
(118)
k→∞
Next, again fix any η > 0. By Claim D.2,
By continuity of G in z2 , for all sufficiently large k, (k)
G(β ⋆ − η, z1 , z2 ) > δ.
(119)
(k)
Thus β ⋆ − η is not feasible for the problem defining βmin (z1 , z2 ). Since G is non-increasing in β, no value β ≤ β⋆ − η is feasible either. Therefore,
(k)
βmin (z1 , z2 ) ≥ β ⋆ − η for all sufficiently large k. Taking the liminf gives (k)
lim inf βmin (z1 , z2 ) ≥ β ⋆ − η. k→∞
Since η > 0 was arbitrary, (k)
lim inf βmin (z1 , z2 ) ≥ β ⋆ . k→∞
Combining the two inequalities, (k)
(k)
lim sup βmin (z1 , z2 ) ≤ β ⋆ ≤ lim inf βmin (z1 , z2 ). k→∞
k→∞
Hence,
(k)
βmin (z1 , z2 ) → β ⋆ = βmin (z1 , z2 ). Therefore, βmin (Nmin1 , Nmin2 ) is continuous in Nmin2 . 23
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
Proof of Claim D.2 Proof. The first inequality in (112) is straightforward from the definition of β ∗ . For the second inequality, we show that for every η > 0 such that β ⋆ + η ≤ 1, G(β ⋆ + η, z1 , z2 ) < δ. 1 Let β0 := β ⋆ and β1 := β ⋆ + η. Since η > 0, we have β1 > β0 . Define α := 1−β 1−β0 . Then 0 ≤ α < 1. Now consider any ′ neighboring pair of private histograms P̄prv and P̄prv . For a fixed noise distribution Pnse , define
Psyn,β = (1 − β)P̄prv + βPnse , and ′ ′ Psyn,β = (1 − β)P̄prv + βPnse .
Then Psyn,β1 = αPsyn,β0 + (1 − α)Pnse , and similarly ′ ′ Psyn,β = αPsyn,β + (1 − α)Pnse . 1 0
For compactness, write P0 := Psyn,β0 ,
′ Q0 := Psyn,β , 0
R := Pnse .
Then P1 := Psyn,β1 = αP0 + (1 − α)R, and ′ Q1 := Psyn,β = αQ0 + (1 − α)R. 1
We now compare the m-fold product distributions. Since P1⊗m = (αP0 + (1 − α)R)
⊗m
,
we can expand7 P1⊗m =
∑︂
⊗|S|
⊗ R⊗(m−|S|) .
⊗|S|
⊗ R⊗(m−|S|) .
α|S| (1 − α)m−|S| P0
S⊆[m]
Similarly, Q⊗m = 1
∑︂
α|S| (1 − α)m−|S| Q0
S⊆[m]
Using convexity of the hockey-stick divergence in the pair of distributions, we obtain ⃦ (︂ )︂ ∑︂ ⊗|S| |S| m−|S| ⊗(m−|S|) ⃦ ⊗|S| ⊗(m−|S|) Eγ (P1⊗m ∥Q⊗m ) ≤ α (1 − α) E P ⊗ R ⊗ R . ⃦Q γ 1 0 0 S⊆[m]
Since the same distribution R⊗(m−|S|) appears under both hypotheses on the coordinates in S c , those coordinates contain no information for distinguishing the two distributions. By data processing, or equivalently by marginalizing out the coordinates in S c , ⃦ ⃦ (︂ )︂ (︂ )︂ c⃦ ⊗|S| ⃦ ⊗|S| ⊗S c Eγ P0⊗S ⊗ R⊗S ⃦Q⊗S ⊗ R = E P . ⃦Q γ 0 0 0 7 Sampling one coordinate from P1 is equivalent to first drawing a Bernoulli variable with success probability α. With probability α, the coordinate is sampled from P0 , and with probability 1 − α, it is sampled from R. For m independent samples, let S ⊆ [m] denote the set of coordinates sampled from P0 . Then the coordinates in S c are sampled from R. The probability of this choice of S is c ⊗|S| α|S| (1 − α)m−|S| , and the corresponding product distribution is P0 ⊗ R⊗|S | . Summing over all subsets S ⊆ [m] gives the stated expansion.
24
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
Therefore, ∑︂
Eγ (P1⊗m ∥Q⊗m 1 )≤
⃦ )︂ (︂ ⊗|S| ⃦ ⊗|S| . α|S| (1 − α)m−|S| Eγ P0 ⃦Q0
S⊆[m]
Grouping subsets by cardinality s = |S|, this becomes Eγ (P1⊗m ∥Q⊗m 1 )≤
m (︃ )︃ ∑︂ m s=0
s
⃦ (︁ )︁ αs (1 − α)m−s Eγ P0⊗s ⃦Q⊗s . 0
For s = 0, the two distributions are identical, so Eγ (P0⊗0 ∥Q⊗0 0 ) = 0. For every 1 ≤ s ≤ m, marginalizing an m-sample observation down to its first s coordinates is a stochastic channel. Hence, by data processing, ⊗m Eγ (P0⊗s ∥Q⊗s ∥Q⊗m 0 ) ≤ Eγ (P0 0 ). Thus, Eγ (P1⊗m ∥Q⊗m 1 )≤ Since
m (︃ )︃ ∑︂ m s=1
s
m (︃ )︃ ∑︂ m s α (1 − α)m−s Eγ (P0⊗m ∥Q⊗m 0 ). s s=1
αs (1 − α)m−s = 1 − (1 − α)m ,
we get ⊗m m Eγ (P1⊗m ∥Q⊗m ∥Q⊗m 1 ) ≤ (1 − (1 − α) ) Eγ (P0 0 ).
Now γ = eε . Therefore, ⃦ ⃦ (︂ )︂ (︂ )︂ ⊗m ⃦ ′⊗m ⊗m ⃦ ′⊗m m ε Eeε Psyn,β ≤ (1 − (1 − α) ) E P . ⃦P ⃦P e syn,β syn,β syn,β 1 1 0 0 ′ This inequality holds for every neighboring pair (Dprv , Dprv ). Taking the supremum over neighboring pairs gives
G(β1 , z1 , z2 ) ≤ (1 − (1 − α)m ) G(β0 , z1 , z2 ). Using β0 = β ⋆ and G(β ⋆ , z1 , z2 ) = δ we obtain, G(β ⋆ + η, z1 , z2 ) ≤ (1 − (1 − α)m ) δ. Since 0 ≤ α < 1 we have 0 < 1 − (1 − α)m < 1 for m ≥ 1 and α > 0. Hence, G(β ⋆ + η, z1 , z2 ) < δ. If α = 0, then β1 = 1, and ′ Psyn,β1 = Psyn,β = Pnse . 1
Therefore, G(1, z1 , z2 ) = 0 < δ. Thus, in all cases, G(β ⋆ + η, z1 , z2 ) < δ
25
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
D.2. Interpretation of Remark 4.5: To analyze the minmax TV distance in the LHS of (11), we split it into two cases.
{︃ min
Pnse ∈∆d
min
max
β∈[0,1] P̄prv ∈Bγ,P̄ pub β≥βmin (Nmin1 ,Nmin1 )
TV(P̄prv , Psyn ) = min
⏟⏟
⏞
∑︁
Pnse ∈S
min
Pnse ∈∆d \S
f (Pnse )
(120)
⏞
f (Pnse )
where S = {P ∈ ∆d :
}︃ min f (Pnse ),
[i]
[i]
i:P̄pub ≤P [i]
P̄pub ≥ γ}, with P [i] denoting the ith element of P in the same order as P̄pub . To
interpret the two regimes for Pnse in (120), consider the simplified version of the LHS of (120) in (5). For a fixed Pnse , the inner max chooses the worst-case P̄prv ∈ Bγ,P̄pub (i.e., farthest from Pnse ). If Pnse ∈ S, this worst-case P̄prv lies on the same line through P̄pub and Pnse , giving TV(Pnse , P̄pub ) + γ for the inner max (Fig. 6: blue). If Pnse ∈ ∆d \ S, the worst-case P̄prv is off that line, so the inner maximum is strictly smaller than TV(Pnse , P̄pub ) + γ (Fig. 6: red). These two cases require different analyses, which is provided in App. F. This results in the two-case structure in Remark 4.5. The Key insight from Remark 4.5 is that the approximation to ∗ the optimal noise distribution P̂nse is always a floor-raised version of P̄pub , where both MIFR(P̄pub , t1 ) and WF(P̄pub , t2 ) raise small elements to their respective thresholds and redistribute probability mass from larger elements. This design balances two objectives: since P̄prv and P̄pub come from the same domain with typically small TV(P̄pub , P̄prv ), choosing Pnse close to P̄pub is beneficial. However, many elements in P̄pub can be small (even zero), which would add minimal noise to [i] corresponding P̄prv elements and require a larger mixing weight β to maintain privacy, pushing Psyn too close to P̄pub (not to ∗ P̄prv ). The optimal Pnse resolves this tradeoff by remaining close to P̄pub while floor-raising smaller probabilities to guaran[i] tee a sufficient p = mini Pnse , which allows a smaller mixing weight β and yields a Psyn that is closer to P̄prv .
Figure 6. The two cases in Remark 4.5 correspond to two sets of potential noise distributions: 1) a worst-case P̄prv in (3) that is on the same line as Pnse and P̄pub ; 2) a worst-case P̄prv that is not on the same line.
E. Proof of Theorem 4.2 Theorem 4.2 restated: Let γ ∈ (0, 1] be a constant and let P̄pub ∈ ∆d be a public distribution. Fix the privacy parameters ε > 0, δ ∈ (0, 1) and the required number of synthetic samples m ≥ 1. Then,
min
Pnse ∈∆d
min
max
β∈[0,1] P̄prv ∈Bγ,P̄ pub β≥βmin (Nmin1 ,Nmin1 )
TV(P̄prv , Psyn ) = min1 βmin (t, t)f (t)
(121)
0≤t≤ d
where f (t) is the solution to the following linear program:
f (t) =
min
Pnse ∈∆d , r∈R
r,
s.t.
r + Pnse (S) ≥ min{P̄pub (S) + γ, 1}, ∀S ⊆ [d],
1Td Pnse = 1,
[i] Pnse ≥ t, ∀i (122)
∗ The corresponding optimum Pnse is the minimizing Pnse of (122) with t = t∗ where t∗ = arg min0≤t≤ d1 βmin (t, t)f (t). ∗ ∗ The optimum β is given by β = βmin (t∗ , t∗ ).
26
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
Proof: We begin the proof by re-writing the LHS of (121) as follows: min
Pnse ∈∆d
min
max
β∈[0,1] P̄prv ∈Bγ,P̄ pub β≥βmin (Nmin1 ,Nmin1 )
min
= min1
min
Pnse ∈∆d [i] mini Pnse =t
0≤t≤ d
0≤t≤ d
Pnse ∈∆d [i] mini Pnse =t
= min1
βmin (t, t)
0≤t≤ d
= min1
P̄prv ∈Bγ,P̄
min
TV(P̄prv , Psyn )
(123)
βTV(P̄prv , Pnse )
(124)
TV(P̄prv , Pnse )
(125)
TV(P̄prv , Pnse )
(126)
pub
max
β∈[0,1] β≥βmin (t,t)
P̄prv ∈Bγ,P̄
min
Pnse ∈∆d [i] mini Pnse =t
βmin (t, t)
0≤t≤ d
max
β∈[0,1] β≥βmin (t,t)
min
= min1
TV(P̄prv , Psyn )
max P̄prv ∈Bγ,P̄
pub
min
Pnse ∈∆d [i] mini Pnse ≥t
pub
max P̄prv ∈Bγ,P̄
pub
where (126) comes from the fact that βmin (t, t) is decreasing in t (see Lemma C.5). Next, we consider the inner maximization in (126). Lemma E.1. For any fixed Pnse ∈ ∆d , [︁ {︁ }︁ ]︁ max TV(P̄prv , Pnse ) = max min P̄pub (S) + γ, 1 − Pnse (S) (127) S⊂[d] 1≤|S|≤d−1
P̄prv ∈Bγ,P̄
pub
∑︁ [i] [i] i∈S Pnse . The cardinality of set S is denoted by |S|, and [d] = {1, . . . , d}. i∈S P̄pub and Pnse (S) =
∑︁
where P̄pub (S) =
The proof of Lemma E.1 is given in Sec. E.1. Using Lemma E.1 in (126), we have, min
Pnse ∈∆d
min
max
β∈[0,1] P̄prv ∈Bγ,P̄ pub β≥βmin (Nmin1 ,Nmin1 )
= min1
βmin (t, t)
0≤t≤ d
min
TV(P̄prv , Psyn )
max
Pnse ∈∆d [i] mini Pnse ≥t
S⊂[d] 1≤|S|≤d−1
[︁ {︁ }︁ ]︁ min P̄pub (S) + γ, 1 − Pnse (S)
(128)
Now, fix t ∈ [0, 1/d], and consider the inner minmax optimization in (128). Let: [︁ {︁ }︁ ]︁ f (t) = min max min P̄pub (S) + γ, 1 − Pnse (S)
(129)
Since P̄pub and γ are given constants, for a given subset S ⊂ [d] satisfying 1 ≤ |S| ≤ d − 1, define: {︁ }︁ CS = min P̄pub (S) + γ, 1
(130)
Pnse ∈∆d [i] mini Pnse ≥t
Then, f (t) = min Pnse ∈∆d
S⊂[d] 1≤|S|≤d−1
[CS − Pnse (S)]. S⊂[d] 1≤|S|≤d−1
max
[i] mini Pnse ≥t
Introduce an auxiliary scalar r representing an upper
bound on the inner maximum. For any fixed Pnse ∈ ∆d , r≥
max S⊂[d] 1≤|S|≤d−1
[CS − Pnse (S)]
⇐⇒ r ≥ CS − Pnse (S),
∀S ⊂ [d],
1 ≤ |S| ≤ d − 1
(131)
Therefore, f (t) =
min
r
s.t.
[i] Pnse ≥ t,
Pnse ∈∆d , r∈R
d ∑︂
∀i
[i] Pnse =1
i=1
Pnse (S) + r ≥ CS ,
∀S ⊂ [d],
Plugging (132) back in (128) completes the proof of Theorem 4.2. ■ 27
1 ≤ |S| ≤ d − 1
(132)
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
E.1. Proof of Lemma E.1 Proof: We first prove that the RHS of (127) is an upper bound for the LHS of (127). Then we show equality via an achievability proof. By the definition of TV distance, we have, max P̄prv ∈Bγ,P̄
TV(P̄prv , Pnse ) = pub
max pub
=
(P̄prv (S) − Pnse (S))
max
P̄prv ∈Bγ,P̄
S⊆[d]
max
(P̄prv (S) − Pnse (S))
max
P̄prv ∈Bγ,P̄
pub
S⊂[d] 1≤|S|≤d−1
(︄ =
(134) )︄
max S⊂[d] 1≤|S|≤d−1
(133)
P̄prv (S) − Pnse (S)
max P̄prv ∈Bγ,P̄
(135)
pub
The set {S ⊂ [d] : 1 ≤ |S| ≤ d−1} in (134) is due to the fact that S = ϕ and S = [d] both result in P̄prv (S)−Pnse (S) = 0, which do not contribute to the maximum. The two maxima in (134) can be switched as the set of subsets in {S ⊂ [d] : 1 ≤ |S| ≤ d − 1} is finite. Next, consider maxP̄prv ∈Bγ,P̄ P̄prv (S). For any P̄prv ∈ Bγ,P̄pub , and any fixed S ⊂ [d] satisfying pub
1 ≤ |S| ≤ d − 1, P̄prv (S) − P̄pub (S) ≤ TV(P̄prv , P̄pub ) ≤ γ
=⇒
P̄prv (S) ≤ P̄pub (S) + γ
(136)
Moreover, since P̄prv (S) ≤ 1, we have, {︁ }︁ P̄prv (S) ≤ min P̄pub (S) + γ, 1
(137)
Since this applies to any P̄prv ∈ Bγ,P̄pub , we have, {︁ }︁ P̄prv (S) ≤ min P̄pub (S) + γ, 1
max P̄prv ∈Bγ,P̄
(138)
pub
for any fixed S ⊂ [d] satisfying 1 ≤ |S| ≤ d − 1. Next, we show this upper bound is achievable. Define: α = min{γ, 1 − P̄pub (S)}
(139)
We will move α probability mass from S c to S where S c = [d] \ S denotes the complement of S. This is feasible because: α ≤ 1 − P̄pub (S) = P̄pub (S c )
(140)
Thus, there’s sufficient mass to be removed from S c . At the same time, there’s sufficient capacity in S to receive α probability mass as α ≤ 1 − P̄pub (S). Now, construct a P̄prv as follows (denote it by P̂prv to avoid confusion): {︄ [i] P̄pub + ai , i ∈ S [i] P̂prv = (141) [i] P̄pub − bi , i ∈ S c ∑︁ [i] where ai are chosen such that 0 ≤ ai ≤ 1 − P̄pub among i ∈ S while satisfying i∈S ai = α, and bi are chosen ∑︁ [i] such that 0 ≤ bi ≤ P̄pub among i ∈ S c while satisfying i∈S c bi = α. Note that these selections are feasible since ∑︁ ∑︁ ∑︁ ∑︁ [i] [i] c i∈S ai ≤ 1 − P̄pub (S) ≤ i∈S (1 − P̄pub ) as |S| ≥ 1, and i∈S c bi ≤ 1 − P̄pub (S) = P̄pub (S ) = i∈S c P̄pub . With the P̂prv in (141), for any S ⊂ [d] satisfying 1 ≤ |S| ≤ d − 1, we have, P̂prv (S) = min{P̄pub (S) + γ, 1}. Since the upper bound in (138) is satisfied with equality in (142), {︁ }︁ max P̄prv (S) = min P̄pub (S) + γ, 1 , P̄prv ∈Bγ,P̄
pub
Plugging (143) back in (135) completes the proof of Lemma E.1. ■ 28
∀S ⊂ [d],
(142)
1 ≤ |S| ≤ d − 1.
(143)
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
F. Details of Remark 4.5 In this section, we provide the reasoning behind our approximation for the optimal noise distribution in Remark 4.5. The main optimization in Theorem 4.2 can be written as, {︃ min
Pnse ∈∆d
min
max
β∈[0,1] P̄prv ∈Bγ,P̄ pub β≥βmin (Nmin1 ,Nmin1 )
TV(P̄prv , Psyn ) = min
min g(Pnse ),
Pnse ∈A
min
Pnse ∈∆d \A
}︃ g(Pnse )
(144)
{︂ }︂ ∑︁ [i] where A = Pnse ∈ ∆d : ≥ γ and, [i] [i] P̄ pub i:P̄ ≤P pub
nse
g(Pnse ) =
min
max
β∈[0,1] P̄prv ∈Bγ,P̄ pub β≥βmin (Nmin1 ,Nmin1 )
TV(P̄prv , Psyn )
(145)
[i]
for any given Pnse ∈ ∆d with mini Pnse = Nmin1 . Next, we consider the two cases Pnse ∈ A and Pnse ∈ Ac in (144) separately. Lemma F.1. For given P̄pub ∈ ∆d and γ ∈ (0, 1), arg min g(Pnse ) = MIFR(P̄pub , t1 )
(146)
Pnse ∈A
[i]
∑︁
where t1 = arg mint∈F βmin (t, t)(γ +
[i]
i:P̄pub ≤t
(t − P̄pub )) with F = {t :
[i]
∑︁
[i]
i:P̄pub ≤MIFR[i] (P̄pub ,t)
P̄pub ≥ γ}.
The proof of Lemma F.1 is given in Sec. F.1. Lemma F.1 characterizes the optimal solution to the first component in the minimization of (144). Next, we analyze the second component. Consider the set of distributions Ac = ∆d \ A. [i]
∑︂
Ac = {Pnse ∈ ∆d :
[i]
P̄pub < γ}
(147)
[i]
i:P̄pub ≤Pnse
Lemma F.2. For given P̄pub ∈ ∆d and γ ∈ (0, 1), WF(P̄pub , t2 ) ∈ Ac , and (︁ )︁ min g(Pnse ) ≤ g WF(P̄pub , t2 )
(148)
Pnse ∈Ac
where t2 = arg mint∈G βmin (t, t)Φ(t) with {︄
Φ(t) =
kt =
∑︁d
max
kt ≤u≤d−1
, and G = {t : [i] i=1 1{P̄pub ≤t}
}︄ u u ∑︂ ∑︂ [i] [i] [i] min γ − (P̄pub − WF (P̄pub , t)), WF (P̄pub , t) i=1
∑︁
(149)
i=1
[i]
[i]
i:P̄pub ≤t
P̄pub < γ}.
The proof of Lemma F.2 is given in Sec. F.2. Combining Lemmas F.1 and F.2 with (144), we have, min
Pnse ∈∆d
min
max
β∈[0,1] P̄prv ∈Bγ,P̄ pub β≥βmin (Nmin1 ,Nmin1 )
{︁ (︁ )︁ (︁ )︁}︁ TV(P̄prv , Psyn ) ≤ min g MIFR(P̄pub , t1 ) , g WF(P̄pub , t2 )
(150)
∗ which corresponds to the suboptimal approximation of Pnse in Remark 4.5.
Fig. 7 shows the histogram of the differences between the objective values (minimax TV distance g(Pnse ) = ∗ minβ≥βmin maxP̄prv ∈Bγ,P̄pub TV(P̄prv , Psyn )) obtained using the optimal noise distribution Pnse from Theorem 4.2 and ∗ the approximation P̂nse from Remark 4.5. The histograms are computed over a grid of public distributions P̄pub , with γ = 0.35, n = 100, m = 80, ε = 5, and δ = 1/n. 29
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
(a) d = 3
(b) d = 4
Figure 7. Histograms over candidate P̄pub distributions, showing the difference between the minimax TV distance g(Pnse ) = ∗ ∗ minβ≥βmin maxP̄prv ∈Bγ,P̄pub TV(P̄prv , Psyn ) considering the optimal Pnse from Theorem 4.2 and the approximation P̂nse in Remark 4.5.
F.1. Proof of Lemma F.1 [i]
Proof: For a fixed Pnse ∈ A with mini Pnse = Nmin1 , g(Pnse ) =
min
max
TV(P̄prv , Psyn )
(151)
TV(P̄prv , Pnse )
(152)
[︁ {︁ }︁ ]︁ min P̄pub (S) + γ, 1 − Pnse (S)
(153)
β∈[0,1] P̄prv ∈Bγ,P̄ pub β≥βmin (Nmin1 ,Nmin1 )
= βmin (Nmin1 , Nmin1 )
max P̄prv ∈Bγ,P̄
pub
Recall from Lemma E.1 that for any fixed Pnse : max
TV(P̄prv , Pnse ) =
P̄prv ∈Bγ,P̄
pub
max S⊂[d] 1≤|S|≤d−1
Note that for any fixed P̄pub ∈ ∆d and Pnse ∈ A, TV(Pnse , P̄pub ) = Pnse (B) − P̄pub (B) [i]
(154)
[i]
where B = {i : P̄pub ≤ Pnse }. Since we are considering Pnse ∈ A, we have, P̄pub (B) ≥ γ
=⇒
P̄pub (B c ) < 1 − γ
Thus, when S = B c , we have, {︁ }︁ min P̄pub (B c ) + γ, 1 − Pnse (B c ) = P̄pub (B c ) + γ − Pnse (B c ) = TV(P̄pub , Pnse ) + γ
(155)
(156)
At the same time, we have: TV(P̄prv , Pnse ) ≤ TV(P̄prv , P̄pub ) + TV(P̄pub , Pnse ) ≤ γ + TV(P̄pub , Pnse )
(157)
Since the upper bound in (157) is satisfied with equality in (156) when S = B c , combining (153), (156), and (157), we get: max
TV(P̄prv , Pnse ) = γ + TV(P̄pub , Pnse )
(158)
g(Pnse ) = βmin (Nmin1 , Nmin1 )(γ + TV(P̄pub , Pnse ))
(159)
P̄prv ∈Bγ,P̄
pub
Continuing from (152), for any Pnse ∈ A,
Consequently, min g(Pnse ) = min1 βmin (t, t)
Pnse ∈A
0≤t≤ d
30
min
Pnse ∈A [i] mini Pnse =t
(γ + TV(P̄pub , Pnse ))
(160)
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
Claim F.3. Consider a fixed P̄pub ∈ ∆d and a fixed t ∈ [0, 1/d]. If MIFR(P̄pub , t) ∈ / A, there exists no other Pnse with [i] mini Pnse = t satisfying Pnse ∈ A. [i]
[i]
Proof: To satisfy mini Pnse = t, we need Pnse ≥ t, ∀i. Note that, ∑︂ [i] arg max P̄pub = MIFR(P̄pub , t) Pnse ∈∆d [i] mini Pnse =t
[i]
(161)
[i]
i:P̄pub ≤Pnse
as MIFR(P̄pub , t) increases the elements of P̄pub below t exactly up to t, and removes the added mass from larger elements of P̄pub such that the unchanged probability mass is maximized (see Def. 4.4). This is the exact definition of maximizing ∑︁ ∑︁ [i] [i] P̄ < γ, [i] [i] P̄ [i] pub while satisfying the floor constraint. Thus, for a given t ∈ [0, 1/d], if i:P̄ ≤P i:P̄ ≤MIFR[i] (P̄ ,t) pub pub
nse
pub
pub
we have, [i]
∑︂ [i] [i] i:P̄pub ≤Pnse
[i]
∑︂
P̄pub ≤
∀Pnse ∈ ∆d ,
P̄pub < γ,
[i] i:P̄pub ≤MIFR[i] (P̄pub ,t)
[i] min Pnse =t i
(162)
[i]
Thus, no other Pnse with mini Pnse = t satisfies Pnse ∈ A for that specific t. ■ For the given P̄pub , let F ⊆ [0, 1/d] be the feasible set of t, for which MIFR(P̄pub , t) ∈ A. In other words, F is the set of t [i] values for which the set A ∩ {Pnse : mini Pnse = t} is non-empty. Then, we can rewrite (160) as, min g(Pnse ) = min1 βmin (t, t)
Pnse ∈A
0≤t≤ d
= min βmin (t, t) t∈F
min
Pnse ∈A [i] mini Pnse =t
min
(γ + TV(P̄pub , Pnse ))
(γ + TV(P̄pub , Pnse ))
Pnse ∈A [i] mini Pnse =t
∑︂
≥ min βmin (t, t)(γ + t∈F
[i]
(t − P̄pub ))
(163) (164) (165)
[i] i:P̄pub ≤t
[i]
as the minimum TV(P̄pub , Pnse ) with the mini Pnse = t constraint is achieved when only the smaller elements of P̄pub are [i] increased to t and the corresponding additional mass is removed from larger P̄pub . At the same time, from the definition of MIFR in Def. 4.4, we have, ∑︂ [i] g(MIFR(P̄pub , t∗ )) = βmin (t∗ , t∗ )(γ + (t∗ − P̄pub )) (166) [i]
i:P̄pub ≤t∗
where t∗ = arg mint∈F βmin (t, t)(γ +
∑︁
[i]
[i]
i:P̄pub ≤t
(t − P̄pub )). This completes the proof of Lemma F.1 as MIFR(P̄pub , t∗ )
achieves the lower bound in (165) with equality. ■ F.2. Proof of Lemma F.2 Proof: Consider the second component in the minimization of (144): min g(Pnse ) =
Pnse ∈Ac
=
min
Pnse ∈Ac
min
min βmin (Nmin1 , Nmin1 )
Pnse ∈Ac
= min1 βmin (t, t) 0≤t≤ d
max
β∈[0,1] P̄prv ∈Bγ,P̄ pub β≥βmin (Nmin1 ,Nmin1 )
max P̄prv ∈Bγ,P̄
TV(P̄prv , Psyn )
(167)
TV(P̄prv , Pnse )
(168)
pub
min
max
Pnse ∈Ac P̄prv ∈Bγ,P̄ pub [i] mini Pnse =t [i]
TV(P̄prv , Pnse )
Next, we characterize the set of t values for which Ac ∩ {Pnse : mini Pnse = t} ̸= ∅. 31
(169)
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation [i]
Claim F.4. For any given P̄pub ∈ ∆d , fix t ∈ [0, 1/d]. If WF(P̄pub , t) ∈ / Ac , then, Ac ∩ {Pnse : mini Pnse = t} = ∅. [i]
Proof: For any Pnse with mini Pnse = t, we have, ∑︂ ∑︂ [i] [i] P̄pub = P̄pub ≥
P̄pub
(170)
[i]
[i]
[i]
[i]
i:P̄pub ≤WF(P̄pub ,t)
i:P̄pub ≤t
i:P̄pub ≤Pnse
[i]
∑︂
from the construction of WF(P̄pub , t) in Def. 4.3. Now, consider the case where WF(P̄pub , t) ∈ / Ac , i.e., ∑︁ [i] [i] P̄ > γ. Then, for any Pnse ∈ ∆d satisfying mini Pnse = t, we have, [i] i:P̄ ≤WF(P̄ ,t) pub pub
pub
[i]
∑︂
γ<
P̄pub =
[i] i:P̄pub ≤WF(P̄pub ,t)
[i]
∑︂ [i] i:P̄pub ≤t
[i]
∑︂
P̄pub ≤
P̄pub
[i] Ac ∩ {Pnse : min Pnse = t} = ∅
=⇒
i
[i] [i] i:P̄pub ≤Pnse
(171)
■ [i]
Claim F.4 states that Ac ∩ {Pnse : mini Pnse = t} ̸= ∅ only for t ∈ G where G = {t :
∑︁
[i]
[i]
i:P̄pub ≤t
P̄pub < γ}. Now, we
continue from (169): min g(Pnse ) = min βmin (t, t)
Pnse ∈Ac
t∈G
= min βmin (t, t) t∈G
= min βmin (t, t) t∈G
= min βmin (t, t) t∈G
= min βmin (t, t) t∈G
min
max
TV(P̄prv , Pnse )
(172)
min c
max
[︁ {︁ }︁ ]︁ min P̄pub (S) + γ, 1 − Pnse (S)
(173)
{︁ }︁ min P̄pub (S) − Pnse (S) + γ, 1 − Pnse (S)
(174)
Pnse ∈Ac P̄prv ∈Bγ,P̄ pub [i] mini Pnse =t Pnse ∈A [i] mini Pnse =t
S⊂[d] 1≤|S|≤d−1
min
max
Pnse ∈Ac [i] mini Pnse =t
S⊂[d] 1≤|S|≤d−1
min c
Pnse ∈A [i] mini Pnse =t
max c
S ⊂[d] 1≤|S c |≤d−1
{︁ }︁ min Pnse (S c ) − P̄pub (S c ) + γ, Pnse (S c )
(175)
min c
max
{︁ }︁ min Pnse (R) − P̄pub (R) + γ, Pnse (R)
(176)
Pnse ∈A [i] mini Pnse =t
R⊂[d] 1≤|R|≤d−1
where (174) follows from Lemma E.1, and R = S c is used for the convenience in notation. [i]
[i]
Claim F.5. For a given Pnse , let L = {i : Pnse ≥ P̄pub }. Then, for any R ⊂ [d], 1 ≤ |R| ≤ d − 1, {︁ }︁ {︁ }︁ min Pnse (R) − P̄pub (R) + γ, Pnse (R) ≤ min Pnse (R ∪ L) − P̄pub (R ∪ L) + γ, Pnse (R ∪ L) [i]
[i]
(177)
[i]
Proof: (177) holds since each i ∈ L contributes to Pnse − P̄pub ≥ 0 and Pnse ≥ 0. ■ [i]
[i]
[i+1]
[i+1]
Assume that the indices are arranged such that P̄pub − Pnse ≤ P̄pub − Pnse , ∀i, and let k(Pnse ) =
∑︁d
. [i] [i] i=1 1{P̄pub ≤Pnse }
Recall that L = {1, . . . , k(Pnse )} for a given Pnse . Then, {︁ }︁ max min Pnse (R) − P̄pub (R) + γ, Pnse (R) R⊂[d] 1≤|R|≤d−1
=
max [i] C⊂{k(Pnse )+1,...,d} 0≤|C|≤d−1−k(Pnse )
{︁ }︁ min Pnse (C ∪ L) − P̄pub (C ∪ L) + γ, Pnse (C ∪ L) {︄
≥
max k(Pnse )≤u≤d−1
u u ∑︂ ∑︂ [i] [i] [i] min γ − (P̄pub − Pnse ), Pnse i=1
(178)
}︄ (179)
i=1 [i]
since only the ordered subsets C are considered in (179). Note that WF(P̄pub , t) ∈ Ac ∩ {Pnse : mini Pnse = t} for any feasible t. Then, k(WF(P̄pub , t)) =
d ∑︂ i=1
1{P̄ [i] ≤WF[i] (P̄ pub
pub
= ,t)}
d ∑︂ i=1
32
1{P̄ [i] ≤t} = kt pub
(180)
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
{︂ }︂ ∑︁u ∑︁u [i] Define Φ(t) = maxkt ≤u≤d−1 min γ − i=1 (P̄pub − WF[i] (P̄pub , t)), i=1 WF[i] (P̄pub , t) , and compute: t2 = arg max βmin (t, t)Φ(t)
(181)
t∈G
[i]
Since WF(P̄pub , t) ∈ Ac ∩ {Pnse : mini Pnse = t}, ∀t ∈ G and t2 ∈ G, we have
(︁ )︁ min g(Pnse ) ≤ g WF(P̄pub , t2 )
(182)
Pnse ∈Ac
■
G. Proof of Corollary 4.6 Corollary 4.6 restated: For any Dprv , m ≥ 1, ε > 0 and δ ∈ (0, 1), the asymptotic solution to (3) with Bγ,S = ∆d is given by, (︃ )︃ 1 min min max TV(P̄prv , Psyn ) = 1 − βmin (1/d, 1/d) (183) Pnse ∈∆d d β∈[0,1] P̄prv ∈∆d β≥βmin (Nmin1 ,Nmin1 ) ∗ are given by, and the corresponding optimum β ∗ and Pnse
1 1d d β ∗ = βmin (1/d, 1/d)
∗ Pnse =
(184) (185)
[i]
[i]
Proof. Let P̄prv and Pnse denote the ith elements of P̄prv and Pnse , respectively. Consider, min
Pnse ∈∆d
min
max TV(P̄prv , (1 − β)P̄prv + βPnse )
β∈[0,1] P̄prv ∈∆d β≥βmin (Nmin1 ,Nmin1 )
d
=
=
min
Pnse ∈∆d
min
Pnse ∈∆d
min β∈[0,1] β≥βmin (Nmin1 ,Nmin1 )
min β∈[0,1] β≥βmin (Nmin1 ,Nmin1 )
β ∑︂ [i] [i] |P̄prv − Pnse | P̄prv ∈∆d 2 i=1 max
β 2
d ∑︂
[i] Pnse + [j]
β (1 − Nmin1 ), 2
(186)
[j] (since min Pnse = Nmin1 ) j
i=1,i̸=arg minj Pnse
(187) = =
β(1 − Nmin1 )
(188)
min βmin (Nmin1 , Nmin1 )(1 − Nmin1 )
(189)
min
Pnse ∈∆d
min β∈[0,1] β≥βmin (Nmin1 ,Nmin2 )
Pnse ∈∆d
From Lemma C.5, we know that βmin (Nmin1 , Nmin1 ) is decreasing in Nmin1 . Then, as βmin (Nmin1 , Nmin1 ) and ∗ 1 − Nmin are both decreasing in Nmin1 , we have the optimal Nmin1 = d1 , and the corresponding optimal Pnse = d1 1d . The resulting minimum TV is given in (183).
H. Extension to General Discrete Distributions In this section, we provide the extension of the privacy constraint when P̄prv and P̄pub are arbitrary discrete distributions (not only normalized histograms). The privacy constraint imposes a lower bound on β for a given Pnse (see Lemma H.1). The same approach in Theorem 4.2 and Remark 4.5 is then taken to obtain the optimum noise distributions. 33
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
Lemma H.1. Fix ε > 0, δ ∈ (0, 1), and the required number of synthetic samples m ≥ 1. Let Pnse ∈ ∆d be any noise [i] [i] distribution and define p := miny∈{1,...,d} Pnse (y) > 0. Define the sensitivity as s = maxi |P̄prv − P¯′ prv |, considering all ′ ′ neighboring private distributions P̄prv , P̄prv corresponding to neighboring datasets Dprv , Dprv . Then, for every β ≥ βmin , the m synthetic samples drawn from Psyn in (1) satisfy the DP constraint in (2).
Proof. Consider the privacy loss random variable (PLRV) in (2):
log
P
m P(YPsyn = {y1 , . . . , ym }) ∑︂ Psyn (yi ) = log ′ ′ P(YPsyn = {y1 , . . . , ym }) Psyn (yi ) i=1
(190)
(y )
i Define L(yi ) = log Psyn ′ (yi ) , which are i.i.d. Note that, syn
Psyn (y) = (1 − β)P̄prv (y) + βPnse (y)
(191)
′ ′ Psyn (y) = (1 − β)P̄prv (y) + βPnse (y)
(192)
where, ′ ′ ′ ′ P̄prv (y) − min{s, P̄prv (y)} ≤ P̄prv (y) ≤ P̄prv (y) + min{s, 1 − P̄prv (y)},
such that
∀y ∈ {1, . . . , d}
(193)
∑︁d
y=1 P̄prv (y) = 1. Then,
1−
′ ′ (y)} (1 − β) min{s, P̄prv (y)} (1 − β) min{s, 1 − P̄prv Psyn (y) ≤ ≤ 1 + ′ ′ ′ Psyn (y) Psyn (y) Psyn (y)
(194)
′ (y) the lower bound simplifies to: Note that if s ≤ P̄prv
1−
(1 − β)s (1 − β)s 1 ≥1− =1− βp ′ Psyn (y) (1 − β)s + βp 1 + (1−β)s
(195)
′ (y) the lower bound simplifies to: If s > P̄prv
1−
′ (y) (1 − β)P̄prv 1 ≥1− βp ′ (1 − β)P̄prv (y) + βp 1 + (1−β)s
(196)
Similarly, the upper bound in (194) is simplified to 1 + (1−β)s βp . Thus, we have, L=1−
P
1 Psyn (y) (1 − β)s ≤ ′ ≤1+ =U βp Psyn (y) βp 1 + (1−β)s
(197)
(y)
U −t Therefore, any t = Psyn ′ (y) can be written as t = θL + (1 − θ)U for θ = U −L ∈ [0, 1]. syn
To satisfy (2), we need:
P
(︄ m ∑︂
)︄ (︃ ∑︁m )︃ [︃ ∑︁m ]︃ P (yi ) P (yi ) λ log syn λ log syn Psyn (yi ) ′ ′ log ′ > ε ≤ δ =⇒ P e i=1 Psyn (yi ) > eλε ≤ e−λε E e i=1 Psyn (yi ) ≤ δ Psyn (yi ) i=1 34
(198)
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
Now, let λ = α − 1 and consider, [︃ ∑︁m ]︃ P (yi ) λ log syn ′ E e i=1 Psyn (yi ) =
m ∑︂ ∏︂
(α−1)
Psyn (yi )e
Psyn (yi ) i=1 log P ′ syn (yi )
∑︁m
(199)
y1 ,...,ym i=1
=
=
= =
m ∑︂ ∏︂
Psyn (yi )
(︄ m )︄α−1 ∏︂ Psyn (yi )
y1 ,...,ym i=1 m ∑︂ ∏︂
i=1
′ (y ) Psyn i
′ Psyn (yi )α Psyn (yi )1−α
i=1 yi m ∑︁ ∏︂ ′ log y Psyn (yi )α Psyn (yi )1−α
e
i=1 m ∏︂
i
′
e(α−1)Dα (Psyn ||Psyn )
(200)
(201)
(202) (203)
i=1 ′
= e(α−1)mDα (Psyn ||Psyn ) From (198), we have the privacy constraint simplified to, (︄ )︃α )︄ (︃ ∑︂ Psyn (y) ′ − (α − 1)ε ≤ log δ m log Psyn (y) ′ (y) Psyn y ′ Note that EPsyn [tα ] =
′ y Psyn (y)
∑︁
(︂
Psyn (y) ′ Psyn (y)
)︂α
(205)
and h(t) = tα is convex. Therefore,
tα = (θL + (1 − θ)U )α ≤ θLα + (1 − θ)U α =⇒
(204)
′ ′ ′ EPsyn [tα ] ≤ EPsyn [θ]Lα + EPsyn [1 − θ]U α
U −1 α 1−L α L + U U −L U −L η+1 1 1 = + (1 + η)α α η + 2 (η + 1) η+2 =
where η = (1−β)s βp . Then, from (205), the privacy constraint simplifies to: (︃ )︃ η+1 1 1 α m log + (1 + η) − (α − 1)ε ≤ log δ η + 2 (η + 1)α η+2
(206) (207) (208) (209)
(210)
Next, (︂we find the optimum α∗ > )︂ 1 that minimizes the LHS of (210) with other parameters fixed. Let f (α) = m log
η+1 1 1 α η+2 (η+1)α + η+2 (1 + η)
η+1 1 1 α − (α − 1)ε and h(α) = η+2 (η+1)α + η+2 (1 + η) . Then,
h′ (α) −ε h(α) η+1 log(η + 1) (η + 1)α h′ (α) = log(η + 1) − (η + 1)−α log(η + 1) = ((η + 1)α − (η + 1)1−α ) η+2 η+2 η+2 log2 (η + 1) h′′ (α) = ((η + 1)α + (η + 1)1−α ) η+2 2m(h′′ (α)h(α) − h′ (α)2 ) m log2 (η + 1) f ′′ (α) = = (η + 1) > 0 h2 (α) h2 (α) (η + 2)2 f ′ (α) = m
(211) (212) (213) (214)
′
(α) Thus, f (α) has a unique minimum at m hh(α) − ε = 0, which simplifies to: (︂ )︂ log(η+1)+ε) log (η+1)(m m log(η+1)−ε α∗ = 2 log(η + 1)
35
(215)
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
which requires ε < m log(η + 1). For ε ≥ m log(η + 1), we can easily show that f ′ (α) < 0 and the optimum α is given by α∗ → ∞, at which f (α) = −∞, satisfying (205) for any β. Note that (215) needs to satisfy α∗ > 1. For this, we need: (︃ (︃ )︃ )︃ (1 − β)s ε 2ε (1 − β)s log 1 + − ≤ βp βp m m
(216)
Since the LHS of (216) is decreasing in β, any β ≥ β̃1 satisfies (216), where β̃1 is the solution to β in (216) with equality. Now, plugging α∗ back in the privacy constraint in (210) gives: (︄ )︄ √︄ (︃ (︃ )︃ )︃ 2m log(η + 1) ε m log(η + 1) + ε η+1 m log − log − log(η + 1) ≤ log δ η+2 2 log(η + 1) m log(η + 1) − ε m2 log2 (η + 1) − ε2 (217) with η = (1−β)s βp . Since the LHS of (217) is decreasing in β, any β ≥ β̃2 satisfies (217), where β̃2 is the solution to β in (217) with equality. Thus, we have, βmin = max{β̃1 , β̃2 }
(218)
where β̃1 , β̃2 are functions of ε, δ, m, n, s, and p = miny∈{1,...,d} Pnse (y).
I. Implementation Details I.1. Implementation Details for the Experiment on Person Activity We evaluate tabular DP synthetic data generation on the Person Activity dataset under a subject-based split to ensure there is no user overlap between private and public data. The dataset contains 164,860 total samples with 5 numerical features and 1 categorical feature, and the prediction target consists of 11 activity classes. We construct the private dataset from users with IDs {1, 2, 4} (107,237 samples) and the public dataset from users with IDs {3, 5} (57,623 samples). Across methods, we consider privacy budgets ε ∈ {1.0, 2.0, 4.0}. We set δ = 1/(n log n), where n is the private dataset size. For the PE-based synthesis pipeline, we use 15 epochs with 3 sampling epochs, generate 5000 samples per sampling stage, and do 3 variations for candidate generation. For the PE+PubMIX variant, we keep the same base configuration and additionally set γ with 0.9. For graphical-model baselines AIM, GSD, and GEM, we use the default configuration with degree=2. For PrivSyn, we use threshold with 20000 and 50 iterations as the default setting. I.2. Implementation Details for the Experiment on Yelp For text synthesis, we use the Yelp reviews corpus as the private training set (approximately 1.9M samples) with the standard dev/test splits. As the generator LLM, we use Llama-2-7B (Touvron et al., 2023) and enable stochastic decoding. Using PE, we run the synthesis procedure for 10 epochs. At each epoch, we generate 5,000 synthetic samples and set the variation degree to 0.5. To support selection via semantic similarity, we embed sentences using Sentence-BERT (Reimers & Gurevych, 2019) and perform nearest-neighbor matching with L2 distance. For privacy accounting, we consider ε ∈ {1, 2, 4} and use the corresponding noise multipliers {15.34, 8.03, 4.24}, respectively. In addition to PE-style synthesis, we include PE+PubMix configured with δ = 10−5 and γ = 0.1. For downstream utility evaluation, we fine-tune a RoBERTa-based classifier/regressor (Liu et al., 2019) on the generated synthetic reviews for two tasks: (i) business category prediction (10-class classification) and (ii) review star prediction (regression over 1–5). We train for 3 epochs with batch size 64, learning rate 3 × 10−5 , and maximum sequence length 64. We select the best checkpoint based on validation performance. We report accuracy for the category task and MAE for the star regression task. The results for the same experiment as in Table 2, with a smaller public dataset (reviews from only MA as opposed to 10 states) is given in Table 3. 36
Optimal Domain-Aware Privacy Mechanisms for Synthetic Data Generation
Table 3. Utility on Yelp Reviews under varying privacy budgets (public dataset = Google reviews from MA). We report mean ± std over multiple runs. Category is classification accuracy (%, higher is better) and Rating is RMSE (lower is better). ε=1
ε=2
ε=4
PE (Xie et al., 2024) P UB M IX
71.67± 0.21 71.03± 0.57
70.69± 0.41 72.02± 0.42
69.93± 0.38 71.63± 0.06
PE (Xie et al., 2024) P UB M IX
0.898± 0.025 0.874± 0.011
0.905± 0.009 0.887± 0.027
0.889± 0.021 0.869± 0.010
Metric
Method
Category (↑) Rating (↓)
37