Keywords: Bayesian nonparametrics; differential privacy; Dirichlet process prior; mechanism informativity, Pitman–Yor process prior; synthetic data generation; \(1\)-Wasserstein posterior contraction rates

1 Introduction↩︎

1.1 Background and motivation↩︎

Over the past three decades, synthetic data generation has become a powerful approach to privacy-preserving statistical analysis, aiming to reconcile data accessibility with the protection of sensitive information [1], [2]. In this framework, a statistical model is fitted to the original confidential data and then used to draw new observations. These simulated or synthetic observations are released in place of the original data, which remain confidential. The effectiveness of such a synthetic data-generating mechanism is governed by a privacy–utility tradeoff: synthetic data should protect sensitive information from disclosure, while preserving enough of the statistical information in the original data to support downstream analyses.

On the privacy side, differential privacy (DP) has become the standard framework for providing formal guarantees of data-release mechanisms. Introduced by [3], DP is now widely adopted in both academia and industry [4]–[7]. At a high level, a mechanism is differentially private if changing a single database record has only a limited effect on its output. On the utility side, once a data-release mechanism has been shown to satisfy DP, it remains essential to assess whether the privatization process preserves enough statistical information from the original data. In this sense, utility requires that the released data remain informative for inference on the confidential data. A general notion of statistical utility for data-release mechanism was proposed by [8], under the name of informativity or consistency. This notion adopts the frequentist perspective that the confidential data are generated from an underlying “true” distribution, and measures utility through the rate at which the expected distance between the empirical measure of the released data and the true data-generating distribution converges to zero. Such a convergence rate provides a natural measure of the quality of the mechanism, quantifying how quickly the released data recover the underlying distribution.

Many private synthetic data-generating mechanisms have been proposed in the literature, ranging from histogram-based methods and exponential-mechanism to more recent approaches based on private-measure release and optimal transport [8]–[13]. Within the Bayesian framework, a natural strategy is to release synthetic observations drawn from a posterior or posterior-predictive distribution [9], [14]–[18]. This is attractive because the data-release mechanism is directly linked to the statistical model used for inference. Specifically, suppose that \(n\geq1\) confidential observations are modeled through a Bayesian model with sampling distribution \(p(\cdot\,|\,\theta)\) and prior distribution \(\pi\): \[\label{eq:bayesmod} X_1,\ldots,X_n \,|\,\theta \overset{\mathrm{iid}}{\sim} p(\cdot \,|\,\theta),\qquad \theta \sim \pi,\tag{1}\] and that \(m\geq1\) observations \(Z_1,\ldots,Z_m\) are drawn from the induced posterior-predictive distribution \[Q_n(\mathrm dz_1,\dots,dz_m\,|\,X_1,\dots,X_n) = \int p^{\otimes m}(\mathrm dz_1,\dots,dz_m \,|\,\theta)\,\pi(\mathrm d\theta\,|\,X_1,\dots,X_n).\] Under the model 1 , the random variables \((X_1,\ldots,X_n,Z_1,\ldots,Z_m)\) are jointly exchangeable, which means that the analyst who receive the synthetic data \((Z_1,\dots,Z_m)\) can analyze it assuming \[Z_1,\ldots,Z_m \,|\,\theta \overset{\mathrm{iid}}{\sim} p(\cdot \,|\,\theta), \qquad \theta \sim \pi,\] without worrying about the privatization step. This contrasts with generic, externally specified DP data-release mechanisms, typically involving a perturbation of the confidential data. As emphasized by [19], valid likelihood-based or Bayesian inference from such released data typically requires integrating over the unobserved confidential sample, leading to intractable likelihoods.

Most existing Bayesian approaches to private synthetic data generation have been developed within parametric models. Such models may be appropriate when the released dataset is designed for a specific inferential task, but they are less satisfactory for general downstream use and, in particular, when the analyses to be performed are not known in advance. Indeed model misspecification may translate directly into a loss of statistical utility: features of the confidential data that are not represented by the chosen parametric family cannot be recovered from the released data. Bayesian nonparametric methods provide a natural alternative. By placing a prior directly on an infinite-dimensional space of probability distributions, they allow the effective complexity of the model to adapt to the data and grow with the sample size, while preserving the posterior and posterior-predictive structure that makes model-aligned release attractive.

1.2 Preview of our contributions↩︎

We develop a Bayesian nonparametric framework for private synthetic data generation tailored to discrete data. By discrete data, we mean observations that may exhibit ties and whose support may contain a large, unknown, or growing number of categories. We model \(n\geq1\) confidential observations as a random sample from an unknown discrete distribution, which is endowed with a Pitman–Yor (PY) process prior [20], [21] with discount parameter \(\sigma\in(-\infty,1)\) and strength parameter \(\theta>-\sigma\). The PY process is particularly natural for discrete data, since it defines a random probability measure with almost surely discrete realizations; consequently, samples from the PY process contain repeated observations with positive probability, while the posterior-predictive distribution allows for the emergence of new categories. Given the \(n\geq 1\) confidential observations modeled as described above, we generate \(m\geq1\) synthetic observations by sampling from the \(m\)-step posterior-predictive distribution induced by the PY process prior; we refer to this synthetic data-generating mechanism as the PY posterior-predictive mechanism. The PY process prior includes two important subcases or regimes: for \(\sigma=0\) it reduces to the Dirichlet process prior [22], while for \(\sigma<0\) it corresponds, at the sampling level, to a parametric Dirichlet–Multinomial model. The PY posterior-predictive mechanism is straightforward to implement, owing to the tractability of the PY posterior-predictive distribution [21], [23]. Moreover, the joint exchangeability of confidential data and synthetic data generated by the mechanism allows standard Markov chain Monte Carlo algorithms to be used for Bayesian inference.

We study DP guarantees of the PY posterior-predictive mechanism. The differentially private behaviour of the mechanism is governed by the discount parameter \(\sigma\), which controls the prevalence of low-frequency categories in the confidential data. Since rare categories are more easily attributable to individual records, low-frequency categories, and singletons in particular, are the main source of privacy risk: if a value appears only once, then releasing that value in the synthetic sample may reveal the contribution of a single individual. In the regime \(\sigma\in[0,1)\), we prove that the PY posterior-predictive mechanism satisfies an instance-level \((\varepsilon,\delta)\)-DP guarantee in the sense of [24]; this privacy guarantee should be viewed as a data-dependent relaxation of the \((\varepsilon,\delta)\)-DP of [3]. In the regime \(\sigma=0\), we establish a \((\varepsilon,\delta)\)-DP bound for the PY posterior-predictive mechanism, with \(\delta\) controlled explicitly by the ratio \(m/n\) between the synthetic and confidential sample sizes. Finally, in the regime \(\sigma<0\), we prove that the PY posterior-predictive mechanism satisfies instance-level \(\varepsilon\)-DP and, under suitable assumptions on the confidential sample size \(m\), it satisfies \(\varepsilon\)-DP [9].

We also investigate the informativity of the PY posterior-predictive mechanism. We quantify informativity of the mechanism through the \(1\)-Wasserstein distance, in line with recent works on differentially private synthetic data-generating mechanisms [11]–[13], [25]–[27]. The \(1\)-Wasserstein distance is well suited to our setting: it applies naturally to discrete probability measures, allows comparison between empirical and population distributions, and remains computationally tractable beyond the univariate case, thereby enabling empirical validation of the proposed data-release mechanism. Moreover, by means of its dual formulation, convergence in \(1\)-Wasserstein distance ensures the preservation of all Lipschitz statistics. For the regimes \(\sigma=0\) and \(\sigma<0\), we prove that PY posterior-predictive mechanism is consistent in \(1\)-Wasserstein distance, with respect to a “true" data-generating distribution, and we derive explicit convergence rates. These rates make precise the privacy–utility tradeoff originally described by [8]: stronger privacy guarantees impose more restrictive choices of the released sample size, which in turn slow down convergence to the”true" data-generating distribution. For \(\sigma=0\), a key step in our analysis consists in bounding the expected \(1\)-Wasserstein distance between a posterior Dirichlet process and its posterior mean. We derive a convergence rate for this expectation, which can be interpreted as a variance term for the posterior Dirichlet process and may be of independent interest.

1.3 Organization of the paper↩︎

Section 2 reviews the background and notation on DP and the PY process prior. Section 3 introduces the PY posterior-predictive mechanism and establishes its main properties, including DP guarantees and \(1\)-Wasserstein consistency results. Section 4 illustrates the methodology with an application to two real datasets. Section 5 discusses limitations of the proposed approach and outlines directions for future research. Proofs and auxiliary technical results are deferred to the appendix.

2 Background and notation↩︎

2.1 Differential privacy↩︎

We first recall the definition of DP [3]. We work in the global DP setting: a trusted curator observes the confidential dataset and then releases a randomized output. This should be distinguished from local DP setting, where each individual randomizes her own record before it is observed by the curator. For \(n\geq 1\), let \(X_1,\ldots,X_n\) be the confidential data, defined on a probability space \((\Omega,\mathcal{A},\mathbb{P})\) and taking values in a Polish space \(\mathbb{X}\) with Borel \(\sigma\)-algebra \(\mathcal{X}\). For \(k\geq 1\), write \(\mathbb{X}^k=\prod_{i=1}^k\mathbb{X}\), and let \(\mathcal{X}^k\) be the corresponding product Borel \(\sigma\)-algebra. The space \(\mathbb{X}\) is often assumed to be bounded; for example, [8] consider \(\mathbb{X}=[0,1]^r\), \(r\geq 1\).

In privacy-preserving statistical analysis, the goal is to construct a data-release mechanism that takes the confidential dataset \(\mathbf{X} := (X_1,\ldots,X_n)\) as input and releases a dataset \(\mathbf{Z} := (Z_1,\ldots,Z_m)\), with each \(Z_i\) taking values in \(\mathbb{X}\), in such a way that individual privacy is protected. In the global DP setting, the dataset \(\mathbf{Z}\) is generated from the entire dataset \(\mathbf{X}\). Formally, the data-release mechanism is a probability kernel \(Q_n(\,\cdot\,|\,\cdot\,):\mathcal{X}^m\times \mathbb{X}^n\to[0,1]\), which gives the conditional distribution of \(\mathbf{Z}\) given \(\mathbf{X}\). The number \(m\) of released observations is a tuning parameter and plays an important role in our results, often characterizing the privacy–utility tradeoff: increasing \(m\) typically improves the utility of the released data, but weakens the privacy guarantees.

DP can be formulated as a stability requirement on the data-release mechanism: changing one record in the confidential dataset should not substantially change the distribution of the released data. Throughout the paper, we use replacement adjacency. In particular, for two datasets \(\mathbf{x},\mathbf{y}\in\mathbb{X}^n\), let \[h(\mathbf{x},\mathbf{y}) = \left|\{i\in\{1,\ldots,n\}:x_i\neq y_i\}\right|\] be their Hamming distance. We say that \(\mathbf{x}\) and \(\mathbf{y}\) are neighbouring, or adjacent, datasets if \(h(\mathbf{x},\mathbf{y})=1\). In the global DP setting, [3] introduced the following notion of DP.

From Definition 1, the parameter \(\varepsilon>0\) measures the strength of the privacy guarantee: smaller values impose stronger privacy, while larger values allow the output distribution to depend more strongly on any single record. The parameter \(\delta \in [0,1)\) controls the probability of privacy losses beyond \(e^\varepsilon\). When Definition 1 holds with \(\delta=0\), the data-release mechanism is said to satisfy \(\varepsilon\)-DP. This notion of privacy admits a clear statistical interpretation: as shown by [8], under \(\varepsilon\)-DP, any level-\(\gamma\) test of \(X_i=s\) versus \(X_i=t\) has power at most \(\gamma e^\varepsilon\).

Definition 1 provides a worst-case privacy guarantee: the same values of \(\varepsilon\) and \(\delta\) must work uniformly over all possible neighbouring datasets, which might be too stringent in some case. We therefore also use a data-dependent relaxation of \((\varepsilon,\delta)\)-DP, in which the privacy requirement is imposed only at the observed dataset. Specifically, condition 2 is required to hold only for \(\mathbf{x}\) and its neighbouring datasets, leading to the following notion, introduced by [24].

For instance-level \((\varepsilon,\delta)\)-DP, the values of \(\varepsilon\) and \(\delta\) may depend on \(\mathbf{x}\). This relaxation still admits an interpretation in terms of hypothesis testing. Suppose that, for a given \(\mathbf{x}\in\mathbb{X}^n\), the data-release mechanism satisfies (2 ) for every \(B\in\mathcal{X}^m\) and every \(\mathbf{y}\in\mathbb{X}^n\) such that \(h(\mathbf{x},\mathbf{y})=1\). Consider an attacker who observes the released data and knows the whole confidential dataset \(\mathbf{X}=\mathbf{x}\), except for the value of one entry \(X_i\). Then any level-\(\gamma\) test of \(H_0:X_i=s\) versus \(H_1:X_i=t\) has power at most \(e^\varepsilon\gamma+\delta\). In practice, \((\varepsilon,\delta)\)-DP can be proved using the notion of \((\varepsilon,\delta)\)-probabilistic DP.

If the Definition [prob95privacy] holds for a fixed \(\mathbf{x} \in \mathbb{X}^n\) and all \(\mathbf{y}\) such that \(\;h(\mathbf{x},\mathbf{y}) = 1\), then the data-release mechanism \(Q_n\) satisfies instance-level \((\varepsilon,\delta)\)-probabilistic DP. [28] prove that \((\varepsilon,\delta)\)-probabilistic DP implies \((\varepsilon,\delta)\)-DP. Similar arguments show the same for instance-level DP guarantees.

2.2 Pitman–Yor process prior↩︎

We next recall the definition of the PY process prior [20], [21] and the sampling properties used throughout the paper [23]. A comprehensive account of the PY process can be found in [29] and the references therein.

Let \(\mathcal{P}(\mathbb{X})\) be the set of probability measures on \(\mathbb{X}\), and let \(H\in\mathcal{P}(\mathbb{X})\) be a non-atomic probability measure. We write \(\tilde{p}\sim\mathscr{PY}(\sigma,\theta,H)\) for a PY process with discount parameter \(\sigma\), strength parameter \(\theta\), and base measure \(H\). The admissible parameter space is given either by \(\sigma\in[0,1)\) and \(\theta>-\sigma\), or by \(\sigma<0\) and \(\theta=z|\sigma|\) for some \(z\in\mathbb{N}\). The definition of the PYP depends on the sign of \(\sigma\):

• if \(\sigma\in[0,1)\), then \[\label{pyp01} \tilde{p}=\sum_{i=1}^{\infty} W_i\delta_{Y_i},\tag{3}\] where \(W_i=V_i\prod_{\ell=1}^{i-1}(1-V_\ell)\), \(V_i\overset{\mathrm{ind}}{\sim}\mathrm{Beta}(1-\sigma,\theta+i\sigma)\) and \(Y_i\overset{\mathrm{iid}}{\sim}H\), independently of \((V_{i})_{i\geq1}\);

• if \(\sigma<0\), then \[\label{pyp} \tilde{p}=\sum_{i=1}^{z}\theta_i\delta_{Y_i},\tag{4}\] for \(z\in\mathbb{N}\), where \((\theta_1,\ldots,\theta_z)\sim \mathrm{Dirichlet}(|\sigma|,\ldots,|\sigma|)\) and \(Y_i\overset{\mathrm{iid}}{\sim}H\), independently of \((\theta_1,\ldots,\theta_z)\).

For every admissible value of \(\sigma\in(-\infty,1)\), the PY process 3 –4 defines a discrete random probability measure on \(\mathbb{X}\); that is, its realizations of the PY process are almost surely discrete probability measures. The structure of its support depends on the sign of \(\sigma\). When \(\sigma\in[0,1)\), the random measure has countably many atoms, with weights given by 3 . The special case \(\sigma=0\), denoted by \(\mathscr{D}(\theta,H)\), is the Dirichlet process with strength parameter \(\theta>0\) and base measure \(H\) [22]. When \(\sigma<0\) and \(\theta=z|\sigma|\) for some \(z\in\mathbb{N}\), the PY process has exactly \(z\) atoms, as in 4 ; at the sampling level, this corresponds to a parametric Dirichlet–Multinomial model.

Because of the discreteness of \(\tilde{p}\sim\mathscr{PY}(\sigma,\theta,H)\), a random sample \(X_1,\ldots,X_n \,|\,\tilde{p} \overset{\mathrm{iid}}{\sim} \tilde{p}\) contains ties with positive probability. Accordingly, the sample induces a random partition of \(\{1,\ldots,n\}\) whose blocks are the classes induced by the equivalence relation \(i\sim j\iff X_{i}=X_{j}\). We denote by \(\{X_1^*,\ldots,X_{K_n}^*\}\) the \(K_n=k_{n}\leq n\) distinct values in the sample, and by \((N_1,\ldots,N_{K_n})=(n_{1},\ldots,n_{k_{n}})\), with \(\sum_{i=1}^{k_{n}}n_{i}=n\), their corresponding frequencies. The random partition induced by a PY process admits a simple sequential construction through the posterior-predictive distribution of \(\tilde{p}\). More precisely, if \(X_{1},\ldots,X_{n}\) is a random sample from \(\tilde{p}\sim\mathscr{PY}(\sigma,\theta,H)\), and \(\mathbb{P}[X_{1}\in\cdot]=H(\cdot)\), then for \(n\geq1\) the posterior-predictive distribution of \(\tilde{p}\) is \[\label{predPy} \mathbb{P}[X_{n+1}\in \cdot \,|\,X_{1},\ldots,X_{n}]=\frac{\theta+\sigma k_n}{\theta+n}H(\cdot)+\sum_{j=1}^{k_n}\frac{n_j-\sigma}{\theta+n}\delta_{X_j^*}(\cdot).\tag{5}\] Thus, \(X_{n+1}\) is either a new value, i.e. not observed in \((X_{1},\ldots,X_{n})\), drawn from \(H\), with probability \[\frac{\theta+\sigma k_n}{\theta+n},\] or it coincides with a previously observed value, say \(X_j^*\) observed in \((X_{1},\ldots,X_{n})\), with probability \[\frac{n_j-\sigma}{\theta+n},\qquad j=1,\ldots,k_n.\] Since \(H\) is non-atomic, a draw from \(H\) generates a new value with probability one. In the finite-atom case \(\sigma<0\), the probability of generating a new value becomes zero when \(K_n=z\), consistently with 4 .

The posterior-predictive distribution 5 , known as the Chinese restaurant process [23], gives an interpretation of \(\sigma\) and \(\theta\). The strength parameter \(\theta\) controls the baseline tendency to generate new values: larger values of \(\theta\) increase the probability of sampling previously unseen categories, especially at small and moderate sample sizes. The discount parameter \(\sigma\) controls the reinforcement mechanism and the growth of the number of distinct values. When \(\sigma=0\), the predictive probability of an old value is proportional to its frequency, and the probability of a new value is \(\theta/(\theta+n)\), as in the Dirichlet process. When \(\sigma>0\), the mass assigned to each observed value is discounted from \(n_j\) to \(n_j-\sigma\), and the total discounted mass \(\sigma k_n\) is transferred to the probability of generating a new value. Thus larger values of \(\sigma\) favour the appearance of new categories and lead to heavier-tailed random discrete distributions. In fact, for \(\sigma\in(0,1)\), the number of distinct values grows polynomially, of order \(n^\sigma\), whereas under the Dirichlet process it grows logarithmically. When \(\sigma<0\), instead, the model has a finite number of possible atoms.

3 Pitman–Yor posterior-predictive mechanism↩︎

For \(n\geq1\), let \(\mathbf{X}=(X_1,\ldots,X_n)\) be the confidential dataset, and assume that \(\mathbf{X}\) is modeled as a random sample from an unknown discrete distribution \(\tilde{p}\) endowed with a PY process prior, namely \[\label{model1} \begin{align} X_1,\ldots,X_n \,|\,\tilde{p} &\overset{\mathrm{iid}}{\sim} \tilde{p},\\ \tilde{p} &\sim \mathscr{PY}(\sigma,\theta,H). \end{align}\tag{6}\] This model is suited to discrete data, since the PY process is a discrete random probability measure and therefore accommodates ties, repeated values, and a potentially large or unknown number of categories. Conditional on \(\mathbf{X}\), we generate a synthetic dataset \(\mathbf{Z}=(Z_1,\ldots,Z_m)\) by sampling sequentially from the posterior-predictive distribution induced by 6 . The procedure relies on the one-step predictive distribution in 5 , iterated \(m\) times, and it is described in Algorithm 1.

We refer to Algorithm 1 as the PY posterior-predictive mechanism. This synthetic data-generating mechanism is straightforward to implement: it only requires sequentially sampling from the PY posterior-predictive distribution 5 . Thus, no dedicated sampling or optimization routine is needed to obtain synthetic data, in contrast with alternative approaches, such as the exponential mechanism of [10], which often require problem-specific implementation.

Before studying the DP guarantees of the PY posterior-predictive mechanism, we clarify the role of the non-atomic base measure \(H\) and the meaning of categories, or distinct values. The data-release mechanism covers two common situations. In the first, the confidential data are real-valued, but the recorded observations exhibit ties because of rounding, finite measurement precision, discretization, or other preprocessing steps. In this case, the categories are simply the distinct recorded values. Since the posterior-predictive distribution may generate previously unseen values, a fixed post-processing map can be applied after sampling if the released data are required to lie on the same recorded scale as the confidential data. This map may merge some of the new categories, possibly with categories already observed in the recorded data, but it does not affect the DP guarantees, provided that it is chosen independently of the confidential data.

In the second situation, the confidential data are categorical, with recorded observations taking values in a set of labels, such as occupations, products, locations, or species names. In this case, each observed label can be encoded by a distinct identifier in \(\mathbb{X}\). The non-atomicity of \(H\) then ensures that, whenever the posterior-predictive distribution selects the \(H\)-component, it generates a new identifier that almost surely does not coincide with any previously observed one. A post-processing step is then needed to map the \(\mathbb{X}\)-valued identifiers back to labels. Identifiers corresponding to observed categories are mapped back to their original labels, whereas new identifiers sampled from \(H\) may be assigned synthetic labels, such as new_category_1, new_category_2, and so on.

3.1 DP guarantees↩︎

The three regimes determined by the sign of the discount parameter \(\sigma\in(-\infty,1)\), namely \(\sigma\in(0,1)\), \(\sigma=0\) and \(\sigma<0\), lead to markedly different DP guarantees for the PY posterior-predictive mechanism. We begin with \(\sigma\in[0,1)\), for which we establish sufficient conditions for instance-level \((\varepsilon,\delta)\)-DP. This weaker notion of privacy is the natural one for \(\sigma\in[0,1)\), where the flexibility of the PY process prior, in terms of \(\sigma\) and \(\theta\), makes uniform control over all datasets too stringent.

Fix a confidential dataset \(\mathbf{x}=(x_1,\ldots,x_n)\) with \(K_n=j\) distinct values \(x_1^*,\ldots,x_j^*\) and frequencies \(\mathbf{n}=(n_1,\ldots,n_j)\), where \(n_i\geq1\), and denote by \(K_m^{(n)}\) the number of new distinct values in the synthetic dataset \(\mathbf{Z}=(Z_1,\ldots,Z_m)\) to be released. In particular, denote by \(S_i:=\sum_{1\leq r\leq m} \mathbf{1}_{\{x_i^*\}}(Z_r)\), for \(i=1,\ldots,j\), the number of times \(x_i^*\) appears in \(\mathbf{Z}\). If \(Q_{\mathbf{x}}\) denotes the conditional distribution of \(\mathbf{Z}\) given \(\mathbf{x}\), then proving that the PY posterior-predictive mechanism satisfies instance-level \((\varepsilon,\delta)\)-DP requires to control the privacy loss between the output distribution \(Q_{\mathbf{x}}\), with density function \(q_n(\cdot\,|\,\mathbf{x})\), and the output distribution corresponding to a neighbouring dataset \(\widetilde{\mathbf{x}}\), with density function \(q_n(\cdot\,|\,\widetilde{\mathbf{x}})\). Namely, we bound the likelihood ratio \(q_n(\mathbf{z}\,|\,\mathbf{x})/q_n(\mathbf{z}\,|\,\widetilde{\mathbf{x}})\) by \(e^\varepsilon\), except on a set \(\mathbf{z}\) having \(Q_{\mathbf{x}}\)-probability at most \(\delta\). This exceptional set is the bad privacy event: on this event, \(\mathbf{Z}\) is too much more likely under \(\mathbf{x}\) than under \(\widetilde{\mathbf{x}}\), and therefore may distinguish the contribution of one individual beyond the allowed privacy level. Every neighbouring dataset is obtained by replacing one occurrence of an old value \(x_l^\ast\) in \(\mathbf{x}\) by a value \(b\neq x_l^\ast\). There are two cases: i) old-to-old replacement, namely \(b\) is another old value, say \(b=x_t^\ast\) with \(t\neq l\); ii) old-to-new replacement, namely \(b\) is a new value, not present among \(x_1^\ast,\ldots,x_j^\ast\).

First consider an old-to-old replacement, in which one occurrence of \(x_l^\ast\) is replaced by \(x_t^\ast\), with \(t \neq l\). In the proof of Theorem 1, we show that the corresponding bad event can be written as \[\mathcal{E}_{l,t}^{\mathrm{old}}(\varepsilon) := \begin{cases} \left\{ \dfrac{n_t-\sigma}{n_t+S_t-\sigma} \dfrac{n_l+S_l-1-\sigma}{n_l-1-\sigma} > e^\varepsilon \right\}, & n_l\ge 2, \\[0.5cm] \{S_l\ge 1\} \cup \left( \{S_l=0\} \cap \left\{ \dfrac{\theta+(j+K_m^{(n)}-1)\sigma}{\theta+(j-1)\sigma} \dfrac{n_t-\sigma}{n_t+S_t-\sigma} > e^\varepsilon \right\} \right), & n_l=1 . \end{cases}\] In the case \(n_l=1\), the replacement deletes \(x_l^\ast\) from \(\widetilde{\mathbf{x}}\). Since \(\mathbf{Z}\) is generated from \(Q_{\mathbf{x}}\), the value \(x_l^\ast\) may still appear in \(\mathbf{Z}\). Thus the event \(\{S_l\ge 1\}\) has positive \(Q_{\mathbf{x}}\)-probability but, because \(H\) is non-atomic, has \(Q_{\widetilde{\mathbf{x}}}\)-probability zero; it is therefore automatically a bad event. On the complementary event \(\{S_l=0\}\), the deleted singleton is not released, so there is no singularity. However, the two posterior-predictive distributions still differ: under \(\mathbf{x}\), there is one more old distinct value, while under \(\widetilde{\mathbf{x}}\) the count of distinct values \(x_t^\ast\) has been increased by one. The residual likelihood ratio is therefore affected by \(K_m^{(n)}\) and by \(S_t\); if many new distinct values are generated, or if few copies of \(x_t^\ast\) are released, the output is relatively more compatible with \(\mathbf{x}\) than with \(\widetilde{\mathbf{x}}\), and the privacy loss may exceed \(\varepsilon\). In the case \(n_l\ge 2\), the label \(x_l^\ast\) remains present after the replacement, so there is no singular event. The privacy loss is instead driven by how the probability mass is allocated between two affected values, say \(x^{\ast}_{l}\) and \(x^{\ast}_{t}\). Under \(\mathbf{x}\), the counts of \(x_l^\ast\) and \(x_t^\ast\) are \(n_l\) and \(n_t\), respectively, whereas under \(\widetilde{\mathbf{x}}\) they are \(n_l-1\) and \(n_t+1\). Hence, \[\dfrac{n_t-\sigma}{n_t+S_t-\sigma} \dfrac{n_l+S_l-1-\sigma}{n_l-1-\sigma}.\] captures the fact that releases with many copies of \(x_l^\ast\) and few copies of \(x_t^\ast\) favour \(\mathbf{x}\) over \(\widetilde{\mathbf{x}}\).

Next consider an old-to-new replacement, in which one occurrence of \(x_l^\ast\) is replaced by a value \(b\notin\{x_1^\ast,\ldots,x_j^\ast\}\). In the proof of Theorem 1, we show that the corresponding bad event can be written as \[\mathcal{E}_l^{\mathrm{new}}(\varepsilon) := \begin{cases} \left\{ \dfrac{\theta+j\sigma}{\theta+(j+K_m^{(n)})\sigma} \dfrac{n_l+S_l-1-\sigma}{n_l-1-\sigma} > e^\varepsilon \right\}, & n_l\ge 2, \\[0.5cm] \{S_l\ge 1\}, & n_l=1, \end{cases}\] whose interpretation is analogous to the one of \(\mathcal{E}_{l,t}^{\mathrm{old}}(\varepsilon)\). The two families of events \(\mathcal{E}_{l,t}^{\mathrm{old}}(\varepsilon)\) and \(\mathcal{E}_l^{\mathrm{new}}(\varepsilon)\) enumerate the releases for which a one-record replacement makes \(\mathbf{Z}\) too likely under \(\mathbf{x}\) relative to a neighbour. Controlling their \(Q_{\mathbf{x}}\)-probabilities controls the instance-level privacy loss.

The quantity \(\delta^\sharp\) can be approximated by Monte Carlo simulation, since 5 provides a direct sampling rule from the PY posterior-predictive distribution. The PY posterior-predictive mechanism can therefore be calibrated as follows. For a prescribed value of \(\varepsilon\) and fixed parameters \((\sigma,\theta)\), one estimates the probabilities in 7 by means of Monte Carlo simulation, thereby obtaining a lower bound on the admissible value of \(\delta\). If this value is acceptable for the application at hand, the synthetic dataset \(\mathbf{Z}\) is released according to Algorithm 1; otherwise, the procedure can be repeated with different choices of \((\sigma,\theta)\). If no choice of parameters yields an acceptable \(\delta\), the mechanism cannot provide the desired DP guarantee for the prescribed \(\varepsilon\). In the special case \(\sigma=0\), the expression for \(\delta^\sharp\) can be made explicit, leading to the next corollary.

The regime \(\sigma=0\) is expected to provide stronger DP guarantees. The reason is that \(\sigma\) governs the growth of the number of distinct values: larger values of \(\sigma\) lead to more low-frequency categories, which are more vulnerable to disclosure and hence weaken privacy protection. The next theorem shows that, under the Dirichlet process prior, the proposed mechanism satisfies \((\varepsilon,\delta)\)-DP.

This result brings to light a structural limit of the PY posterior-predictive mechanism. The lower bound \(\bar\delta_{n,m}(\varepsilon)\) in Theorem 2 is defined as the maximum of two terms. The second term, \(2m/((\theta+n)(e^\varepsilon-1))\), as expected in standard DP mechanisms, decays as \(\varepsilon\) increases; however, the first term, the singleton contribution \(m/(\theta+n+m-1)\), is independent of \(\varepsilon\). Therefore, increasing \(\varepsilon\) beyond a certain value does not lead to a decrease in \(\bar \delta\), which plateaus at the value \(m/(\theta+n+m-1)\). This means that accounting for singletons leads to disruption of the classic differential privacy trade-off between \(\varepsilon\) and \(\delta\): accepting a larger \(\varepsilon\) does not allow to obtain \(\delta\) arbitrarily close to zero. It is also impossible to arbitrarily increase the released sample size \(m\) by increasing \(\varepsilon\).

We finally turn to the regime \(\sigma\in(-\infty,0)\). Here the model 6 corresponds to a parametric Dirichlet–Multinomial model with at most \(z=\theta/|\sigma|\) distinct atoms. This structural constraint improves the DP guarantees of the PY posterior-predictive mechanism, as formalized in the next corollary.

Under the parameter specification of Corollary 2, the PY posterior-predictive mechanism reduces to the Dirichlet-Multinomial data-release mechanism of [9]; see also [8]; see Appendix 6.2. Taking the infimum in 9 over all datasets (corresponding to the worst-case scenario of a singleton), we obtain global \(\varepsilon\)-DP, recovering the condition \(m \leq |\sigma|(e^{\varepsilon}-1)\) from [9]. In the regime \(\sigma\in(-\infty,0)\), the condition 9 is closely related to the condition used by [8], namely \[\alpha_i+C_i \geq \frac{m}{e^\varepsilon-1},\] where \(C_i\) is the count in the \(i\)th histogram bin for the confidential dataset \(\mathbf{X}\), and \(\alpha_i\) is the \(i\)-th parameter of the Dirichlet distribution, \(i=1,\ldots,j\). Overall, our DP guarantees highlight a privacy–flexibility tradeoff for the PY posterior-predictive mechanism, with respect to the values of the discount parameter \(\sigma\in(-\infty,1)\): moving from \(\sigma<0\) to \(\sigma=0\) and then to \(\sigma\in(0,1)\) the model becomes increasingly flexible, but the associated privacy guarantees progressively weaken.

3.2 Mechanism informativity↩︎

Having established DP guarantees for the PY posterior-predictive mechanism, we now turn to the utility of the synthetic data to be released. We adopt the frequentist notion of mechanism informativity introduced in [8]. Assuming that \(X_1,\ldots,X_n \overset{\mathrm{iid}}{\sim} \mathfrak p_0\), for some “true" data-generating distribution \(\mathfrak p_0\), and that the user has access to the synthetic dataset \(\mathbf{Z}=(Z_{1},\ldots,Z_{m})\) but not to the original confidential data \(\mathbf{X}=(X_{1},\ldots,X_{n})\), we explore how inference based on \(\mathbf{Z}\) is informative about aspects of \(\mathfrak p_0\). This distinction is important in practice: a mechanism that releases data with negligible statistical information may provide strong DP guarantees, but it is of little inferential value. We therefore ask whether the empirical distribution of synthetic data converges to the”true" data-generating distribution as the sample size \(m\) grows. Under the frequentist setup, the marginal distribution of \(\mathbf{Z}\) is then the probability measure \[\label{marginal95nu} \nu_{n,m}(A):=\int_{\mathbb{X}^n}Q_n(A\,|\,\mathbf{X}=\mathbf{x})\,\mathfrak p_0(dx_1)\cdots \mathfrak p_0(dx_n),\tag{10}\] for all \(A\in\mathcal{X}^m\). We allow the number of synthetic observations to depend on the size \(n\) of the confidential dataset, writing \(m=m(n)\). Accordingly, asymptotic statements as \(n\to\infty\) implicitly involve the corresponding sequence of sample sizes \(m(n)\). Once a relationship between \(m\) and \(n\) has been specified, we write \(\nu_n\) in place of \(\nu_{n,m}\) for the marginal distribution in 10 . Let \[e_m^{(\mathbf{Z})}:=\frac{1}{m}\sum_{i=1}^m \delta_{Z_i}\] denote the empirical measure of the synthetic data \(\mathbf{Z}\). [8] give the following definition of mechanism informativity, which provides a natural measure of the quality of the mechanism.

Definition 4 is formulated for a generic distance between probability measures. In this work, we specialize it to the \(1\)-Wasserstein distance. We recall the general definition of the \(p\)-Wasserstein distance; see, e.g., [30] and [31]. Let \((\mathbb{X},d_{\mathbb{X}})\) be a complete separable metric space. For \(p\geq1\) and \(\gamma_1,\gamma_2\in\mathcal{P}_p(\mathbb{X})\), the \(p\)-Wasserstein distance is defined as \[\label{wasserstein} \mathcal{W}_p^{\mathcal{P}_p(\mathbb{X})}(\gamma_1,\gamma_2):=\inf_{\xi\in\Pi(\gamma_1,\gamma_2)}\left(\int_{\mathbb{X}^2} d_{\mathbb{X}}(x,y)^p\,\xi(dx,dy)\right)^{1/p},\tag{11}\] where \[\mathcal{P}_p(\mathbb{X}):=\left\{\gamma\in\mathcal{P}(\mathbb{X}):\int_{\mathbb{X}} d_{\mathbb{X}}(x,x_0)^p\,\gamma(dx)<\infty\text{ for some } x_0\in\mathbb{X}\right\}.\] Here, \(\Pi(\gamma_1,\gamma_2)\) denotes the set of couplings of the probability measures \(\gamma_1\) and \(\gamma_2\), that is, the set of probability measures on \((\mathbb{X}^2,\mathcal{X}^2)\) with marginals \(\gamma_1\) and \(\gamma_2\). Throughout the paper we assume that \(\mathbb{X}\) is totally bounded, so that \(\mathcal{P}_p(\mathbb{X})=\mathcal{P}(\mathbb{X})\) holds for every \(p\geq1\). When the underlying space is clear from the context, we omit the superscript \(\mathcal{P}_p(\mathbb{X})\) in \(\mathcal{W}_p^{\mathcal{P}_p(\mathbb{X})}\) and simply write \(\mathcal{W}_p\).

For \(\mathbb{X}\subseteq\mathbb{R}^d\), rates for \(\varepsilon_{n,1}(\mathbb{X},\mathfrak p_0):=\mathbb{E}_{\mathfrak p_0^n}[\mathcal{W}_1(e_m^{(\mathbf{X})},\mathfrak p_0)]\) are already available from [32]; see Appendix 6.3. In our setting, the additional difficulty in verifying Definition 4 is that the empirical measure is computed from the synthetic data \(\mathbf{Z}\), rather than from the original confidential data \(\mathbf{X}\). It is also important to ensure that the DP guarantees of a data-release mechanism are preserved as \(n\to\infty\). This imposes constraints on the growth of \(m=m(n)\) relative to \(n\), and these constraints play a crucial role in the mechanism informativity. We therefore establish \(1\)-Wasserstein consistency for the two regimes in which the PY posterior-predictive mechanism provides satisfactory DP guarantees, namely \(\sigma\in(-\infty,0)\) and \(\sigma=0\). Although the PY posterior-predictive mechanism for \(\sigma\in(-\infty,0)\) has already appeared in the literature [9], its consistency in the sense of Definition 4 has not been established.

Now consider the setting of Theorem 3 and assume further that \(m\asymp n\). It turns out that the condition \[\label{priv95cond} \alpha_i + C_i \geq m / (e^\varepsilon - 1) \text{ for all }i=1,...,z\tag{12}\] required in the Dirichlet–Multinomial regime to satisfy instance-level \(\varepsilon\)-DP is met asymptotically. Indeed, as \(n\to\infty\), the bin counts \(C_i\), \(i=1,\ldots,z\), diverge. To see this, assume that \(\mathfrak p_0=\mathscr T(\theta_0)\), where \(\mathscr T:\Theta\to\mathcal{P}(\mathbb{X})\) is a bijective parametrization map and \(\theta_0=(\theta_{0,1},\ldots,\theta_{0,z})\). Then \((C_1,\ldots,C_z)\sim\mathrm{Multinomial}(n,\theta_0)\), so that each \(C_i\) is marginally distributed as a binomial random variable with parameters \((n,\theta_{0,i})\). Therefore, by Chebyshev’s inequality, \[\mathbb{P}\left(\left|C_i/n-\theta_{0,i}\right|>\varepsilon\right)\leq\frac{\theta_{0,i}(1-\theta_{0,i})}{n\varepsilon^2}\to 0.\] Thus, provided \(\theta_{0,i}>0\), each \(C_i\) grows linearly with \(n\), at least in probability. Therefore, when \(m\asymp n\), Theorem 3 yields \[\mathbb{E}_{\nu_n}\left[\mathcal{W}_1\left(e_m^{(\mathbf{Z})},\mathfrak p_0\right)\right]= \begin{cases} O(n^{-1/2}), & d<2,\\ O(n^{-1/2}\log(1+n)), & d=2,\\ O(n^{-1/d}), & d>2. \end{cases}\] This result shows that, under the Dirichlet–Multinomial regime, the PY posterior-predictive mechanism is informative with the same rate as that obtained by [32]. In this regime, replacing the confidential data by synthetic data therefore entails no loss in the consistency rate.

We next extend Theorem 3 from the regime \(\sigma\in(-\infty,0)\) to the regime \(\sigma=0\). For \(\sigma=0\), the Dirichlet process prior is no longer supported on a fixed finite set of atoms, but allows for countably many possible categories and for the appearance of new values in the synthetic sample. This additional flexibility requires a separate argument to establish \(1\)-Wasserstein consistency.

We now consider the problem of specifying the asymptotic relation between the private sample size \(n\) and the synthetic sample size \(m=m(n)\). Since the term \(\tilde{\delta}\) in Theorem 2 is of order \(O(m/n)\), the asymptotic validity of the assumptions ensuring \((\varepsilon,\delta)\)-DP imposes restrictions on the growth of \(m\) relative to \(n\). One possibility is to fix a target privacy level \(\delta\in(0,1)\) and let \(m\asymp n\), with a sufficiently small proportionality constant. Indeed, if \(m=\lfloor \alpha n\rfloor\), then it holds that \[\limsup_{n\to\infty} \bar\delta_{n,m}(\varepsilon)\leq\max\left\{\frac{\alpha}{1+\alpha},\frac{2\alpha}{e^\varepsilon-1}\right\}.\] Therefore, any choice of \(\alpha<\min\{\delta/(1-\delta),\delta(e^\varepsilon-1)/2\}\) ensures \((\varepsilon,\delta)\)-DP for all sufficiently large \(n\).

If we make the stronger requirement \(\bar{\delta}_{n,m}\rightarrow0\) as \(n \to +\infty\), so that \(\varepsilon\)-DP holds asymptotically, then we need to assume \(m=o(n)\). In particular if \(m \asymp \frac{n}{\log n}\), then we have the following corollary

In the regime \(\sigma=0\), the PY posterior-predictive mechanism is informative with respect to the \(1\)-Wasserstein metric. More precisely, it is informative with rate of convergence 13 when regarded as an \((\varepsilon,\delta)\)-DP mechanism, and with rate of convergence 14 when regarded as an asymptotically \(\varepsilon\)-DP mechanism. In the former case, the weaker DP requirement leads to a faster convergence rate, which is minimax optimal. Thus, under \((\varepsilon,\delta)\)-DP, replacing the confidential data by synthetic data entails no loss in the rate of convergence of the empirical measure to the data-generating distribution. This behaviour illustrates the general phenomenon, emphasized by [8], that DP constraints may slow down convergence rates. At the same time, our results address their question on whether minimax rates can be obtained under DP constraints, showing that they can be achieved by assuming the weaker \((\varepsilon,\delta)\)-DP.

Theorems 3 and 4 also imply corresponding bounds for the expected distance between the synthetic empirical measure and the empirical measure of the confidential data. Indeed, by the triangle inequality, \[\mathbb{E}\left[ \mathcal{W}_1\left(e_m^{(\mathbf{Z})},e_n^{(\mathbf{X})}\right) \right] \leq \mathbb{E}\left[\mathcal{W}_1\left(e_m^{(\mathbf{Z})},\mathfrak p_0\right) \right] + \mathbb{E}\left[\mathcal{W}_1\left(e_n^{(\mathbf{X})},\mathfrak p_0\right) \right].\] This empirical-to-empirical target is considered by [11]. Their mechanism satisfies pure \(\varepsilon\)-DP for every \(n\) and obtains a Wasserstein error of order \(n^{-1/d}\), up to logarithmic factors. By contrast, in Corollary 4 we establish the same rates, but under the weaker finite-sample guarantee \((\varepsilon,\delta_n)\)-DP with \(\delta_n\to0\). The improvement in [11] comes at the price of a more involved construction based on superregular random walks, whereas the PYP posterior-predictive mechanism retains the the structure of the Bayesian nonparametric model.

The proof of Theorem 4 relies on a concentration bound for the posterior distribution of a Dirichlet process, which may be of independent interest. The key quantity is the expected \(1\)-Wasserstein distance between a posterior Dirichlet process and its corresponding posterior mean measure. This term can be interpreted as a Wasserstein analogue of a posterior variance of the Dirichlet process, measuring how tightly the posterior random measure concentrates around its mean.

Interestingly, Lemma 1 implies, by means of triangle inequality, that the same rate is achieved by \[\label{pcr} \mathbb{E}_{\mathfrak{p}_{0}^{n}}\left( \mathcal{W}_{1}^{\mathcal{P}(\mathcal{P}\left( \mathbb{X})\right) }\left( \pi _{n}\left( \cdot |X_1,...,X_n\right) ,\delta _{\mathfrak{p}_{0}}\right) \right)\tag{16}\] which is a posterior contraction rate at \(\mathfrak{p}_0\) for the Dirichlet process prior. Rates of the form in (16 ) have been studied by [33], though their techniques yield a slower rate than 15 .

4 Numerical illustrations↩︎

We report three numerical experiments. The first one illustrates the main computational advantage of posterior-predictive release for downstream Bayesian inference. The second one validates the Wasserstein informativity rates of Theorem 4 in a controlled simulation. The third one compares distributional utility on a large real dataset from the American Community Survey.

4.1 Downstream Bayesian inference↩︎

Recall that under the Dirichlet-process posterior-predictive mechanism, the released data can be analyzed with the ordinary Dirichlet-process posterior. Indeed, if \(Z_1,\ldots,Z_m\) are the released observations, then the downstream posterior is available in closed form: \[\tilde{p} \,|\,Z_1,\ldots,Z_m=z_1,\ldots,z_m \sim \mathscr D\left(\theta+m,\frac{\theta H+\sum_{\ell=1}^{m}\delta_{z_\ell}}{\theta+m}\right).\] Thus posterior summaries can be computed by direct posterior simulation from a standard Dirichlet-process posterior.

This is in sharp contrast with generic synthetic-data mechanisms. Consider, for instance, the perturbed histogram mechanism reviewed in Appendix 6.2. Let \(B_1,\ldots,B_k\) be the histogram partition, let \(C_j=\sum_{i=1}^{n}\mathbb{1}[X_i\in B_j]\), and let \(\tilde{f}\) be the perturbed histogram density obtained from the noisy counts. If \(Z_1,\ldots,Z_m\) are then sampled from \(\tilde{f}\), the correct Bayesian posterior is not the ordinary posterior given \(Z_1,\ldots,Z_m\). Rather, it is the mechanism-aware posterior associated with the hierarchical model \[\tilde{p} \sim \mathscr D(\theta,H),\qquad X_1,\ldots,X_n \,|\,\tilde{p} \stackrel{\scriptsize iid}{\sim}\tilde{p},\qquad C_j=\sum_{i=1}^{n}\mathbb{1}[X_i\in B_j],\qquad Z_1,\ldots,Z_m \,|\,\tilde{f} \stackrel{\scriptsize iid}{\sim}\tilde{f}.\] Consequently, posterior computation requires augmenting the Markov chain with the unobserved confidential sample \(X_{1:n}\), and then updating the Dirichlet process conditionally on the imputed confidential data: \[\tilde{p} \,|\,X_1,\ldots,X_n \sim \mathscr D\left(\theta+n,\frac{\theta H+\sum_{i=1}^{n}\delta_{X_i}}{\theta+n}\right).\] The latent state therefore scales with the confidential sample size \(n\), not with the released sample size \(m\). This makes the exact mechanism-aware posterior computation rapidly infeasible. In our reference implementation, for \(n=10^4\) and \(m=10^2\), obtaining \(1000\) posterior samples from the full \(X_{1:n}\)-augmented MCMC takes about six minutes, making it unfeasible in the intended large-scale regime, where \(n\) may be \(10^6\) or larger.

For this reason, in the repeated simulation below we do not use the full \(X_{1:n}\)-augmented posterior for the histogram sample-release mechanisms. Instead, we use a computational fallback that is deliberately favorable to the histogram mechanisms: we replace the synthetic sample from the histogram by a direct release of the histogram output. This reduces the latent state from the full confidential sample \(X_{1:n}\) to the confidential bin counts. For the perturbed histogram, a direct release of noisy counts is a valid differentially private release when the noise is calibrated to the sensitivity of the count vector. For the smoothed histogram, however, directly releasing the smoothed histogram is not differentially private, except in the degenerate case of complete smoothing, which has no utility. The direct smoothed histogram should therefore be understood only as a non-private computational diagnostic.

We run the fallback simulation on \(n=2000\) confidential observations generated from a discrete distribution on a regular grid in \([0,1]\). The grid probabilities are generated from a mixture of beta-shaped weights, as described in Appendix 8. We compare the downstream posterior summaries obtained from three workflows: the Dirichlet-process posterior-predictive mechanism, the direct perturbed histogram, and the direct smoothed histogram. Posterior samples are used to estimate the mean, the quartiles, and the right-tail probability \(\tilde{p}((0.75,1])\). We report empirical bias, root mean square error, average credible-interval length, frequentist coverage, wall-clock time, and effective sample size per second. Complete results are given in Appendix 8. The statistical accuracy of the three methods is comparable in this simplified experiment, but the computational workflows are not: the proposed posterior-predictive mechanism requires only the standard Dirichlet-process posterior update, whereas the histogram-based workflows require mechanism-aware inference even in the reduced direct-histogram formulation.

4.2 Convergence analysis for a simulated dataset↩︎

We now validate empirically the Wasserstein informativity rates proved in Theorem 4. The confidential data are generated from an explicitly discrete distribution on \([0,1]\), constructed as follows. Let \(G\) have a geometric distribution on \(\{1,2,\ldots\}\) with success probability \(p=0.05\). For \(k\geq 1\), set \(r(k)=\lfloor \log_2 k \rfloor+1\), and define \[T(k)=\frac{2(k-2^{r(k)-1})+1}{2^{r(k)}}.\] Thus \(T(1)=1/2\), \(T(2)=1/4\), \(T(3)=3/4\), \(T(4)=1/8\), and so on. We generate \(N=1000000\) iid observations \(G_1,\ldots,G_N\), and set \(X_i=T(G_i)\). The resulting population sample takes values in the dyadic points of \([0,1]\), contains ties by construction, and has a large but sparse support.

The dataset of size \(N\) is treated as the confidential population. For each value of \(n\) in a grid between \(10000\) and \(N\), we draw a random subsample \(X_1,\ldots,X_n\) and generate a synthetic dataset \(Z_1,\ldots,Z_m\) using the Dirichlet-process posterior-predictive mechanism with base measure \(H=\operatorname{Unif}[0,1]\) and strength parameter \(\theta\). Throughout this section we consider the Pitman–Yor posterior-predictive mechanism in the special case \(\sigma=0\), and refer to it as the Dirichlet-process posterior-predictive mechanism.

The synthetic sample size \(m\) is chosen according to the privacy regime under consideration. For \((\varepsilon,\delta)\)-differential privacy, we set \(\varepsilon=2\) and consider \(\delta\in\{10^{-2},10^{-3},10^{-4}\}\); for each \(n\), \(m\) is chosen as the largest value satisfying the finite-sample bound of Theorem 2. We also consider the asymptotic \(\varepsilon\)-differential privacy regime of Corollary 14 , using a sequence \(m=m(n)\) with \(m/n\to 0\). For each configuration, we compute the \(1\)-Wasserstein distance between the synthetic empirical measure and the empirical measure of the confidential subsample, \[\mathcal{W}_1\left(e_m^{(\mathbf{Z})},e_n^{(\mathbf{X})}\right),\] and average the result over \(100\) independent runs of the synthetic-data generation process.

Figure 2 displays the results for \(\theta\in\{1,10,100\}\). In the three \((\varepsilon,\delta)\)-differentially private scenarios, the decay is close to the \(n^{-1/2}\) benchmark on the log-log scale, in agreement with Corollary 3. In the asymptotic \(\varepsilon\)-differential privacy regime, the convergence is slower, consistently with Corollary 14 . Although the asymptotic \(\varepsilon\)-DP curve can lie below some of the finite-\(\delta\) curves for the sample sizes considered here, this does not contradict the theory: pure \(\varepsilon\)-DP is only obtained asymptotically in this regime, and the finite-sample value of the corresponding \(\delta\) is larger than \(10^{-2}\).

4.3 Real data: California census dataset↩︎

We finally assess distributional utility on a large real dataset. We consider the \(2024\) \(5\)-Year Public Use Microdata Sample from the American Community Survey, conducted by the U.S. Census Bureau [34], and focus on the PINCP variable, which records personal annual income. Observations with missing or non-positive income are removed. The remaining values are transformed logarithmically and then rescaled to \([0,1]\). The resulting dataset contains \(11918162\) observations and \(32393\) distinct recorded values, of which \(7689\) are singletons.

We compare the Dirichlet-process posterior-predictive mechanism with the perturbed histogram and smoothed histogram mechanisms reviewed in Appendix 6.2. The confidential data are modeled with a Dirichlet process prior with base measure \(H=\operatorname{Unif}[0,1]\) and \(\theta=1\). We set \(\varepsilon=2\) and \(\delta=10^{-5}\). Under Theorem 2, the largest admissible released sample size is \(m=119\). This is a stringent privacy regime: the number of released observations is tiny compared with the confidential sample size.

For the histogram mechanisms, we use the same number \(m=119\) of released synthetic observations and \(300\) histogram bins. To match the \((\varepsilon,\delta)\)-privacy target, the perturbed histogram uses Gaussian perturbations of the histogram counts calibrated to the sensitivity of the count vector. For the smoothed histogram, we compose the smoothing step with an \((\varepsilon,\delta)\)-differentially private Gaussian perturbation of the counts. We then generate synthetic datasets from the resulting private histograms.

We evaluate distributional utility in three ways. First, we compare standard summary statistics of the confidential and synthetic datasets: mean, standard deviation, and quartiles. Second, we compare kernel density estimates computed from the confidential and synthetic samples. Third, over \(100\) independent runs of each mechanism, we compute the \(1\)-Wasserstein distance between the synthetic empirical measure and the empirical measure of the confidential data.

Table 1 shows that all three mechanisms preserve the main one-dimensional summaries reasonably well, despite the small value of \(m\). The large confidential sample size makes the histogram mechanisms particularly favorable in this example: most bin counts are large, so the perturbation added to the counts has a limited effect, and the smoothed histogram does not need to over-smooth the distribution. The Dirichlet-process posterior-predictive mechanism nevertheless remains competitive, without requiring a fixed histogram partition.

Figures 3 and [fig:wass95boxplots] give a similar picture. The kernel density estimates obtained from the three synthetic samples are close to the estimate based on the confidential data, and the average \(1\)-Wasserstein distance is below \(0.0125\) for all mechanisms. Thus, on this large real dataset, the proposed mechanism achieves distributional utility comparable to the histogram-based methods under the same released sample size.

5 Discussion↩︎

We have proposed a Bayesian nonparametric framework for private synthetic data generation tailored to discrete data. The mechanism is model-aligned: synthetic observations are drawn directly from the posterior-predictive distribution of the Bayesian nonparametric model. Hence, under the model, confidential and synthetic data are jointly exchangeable, allowing standard Bayesian inference to be carried out from the released data. This contrasts with generic externally specified privatization mechanisms, for which likelihood-based or Bayesian inference may require integrating over the unobserved confidential sample and can become computationally intractable. The proposed mechanism is also simple to implement, since sampling from the PY posterior-predictive distribution is straightforward. At the same time, because the PY process is naturally suited to discrete data with ties and possibly many categories, extensions to data without ties or to mixed discrete-continuous settings remain important directions for future work.

The DP guarantees of the PY posterior-predictive mechanism depend on the discount parameter \(\sigma\in(-\infty,1)\), which controls the prevalence of low-frequency categories and hence the main source of privacy risk. In the regime \(\sigma\in(0,1)\), the mechanism satisfies instance-level \((\varepsilon,\delta)\)-DP. Stronger guarantees are obtained in the two special regimes: for \(\sigma<0\), corresponding to a parametric Dirichlet–Multinomial model, the mechanism satisfies instance-level \(\varepsilon\)-DP and, under suitable conditions on the released sample size, global \(\varepsilon\)-DP [9]; for \(\sigma=0\), corresponding to the Dirichlet process prior, it satisfies global \((\varepsilon,\delta)\)-DP, with \(\delta\) controlled by the ratio between the synthetic and confidential sample sizes. These results show that DP guarantees are strongly tied to the predictive structure induced by the prior, suggesting the study of alternative priors and privacy notions better adapted to posterior-predictive mechanisms.

The utility results provide a frequentist validation of the PY posterior-predictive mechanism. Following the notion of informativity in [8], we measure utility by the expected \(1\)-Wasserstein distance between the synthetic empirical distribution and the “true” data-generating distribution. In the regimes \(\sigma=0\) and \(\sigma<0\), we prove consistency in this metric and derive explicit convergence rates. These rates quantify the privacy–utility tradeoff: stronger privacy requirements may restrict the released sample size and slow convergence to the “true” distribution. When \((\varepsilon,\delta)\)-DP is imposed only asymptotically, however, synthetic data achieve the same consistency rate as the confidential data. As a byproduct, we obtain a concentration bound for the posterior Dirichlet process around its posterior mean in expected \(1\)-Wasserstein distance, leaving analogous results for other Bayesian nonparametric priors as an open question.

Supplementary material to: Bayesian Nonparametric Privacy-Preserving Synthetic Data Generation↩︎

6 Additional theory↩︎

6.1 Additional background material on Pitman–Yor process↩︎

The update rule of the Pitman–Yor process is given by the following proposition ([35]):

6.2 Other privacy mechanisms↩︎

We describe three privacy mechanisms known in the literature. They all rely on generating synthetic data by sampling from a histogram.

We consider \(\mathbb{X} = [0,1]^r\) for some integer \(r \geq 1\) and partition \(\mathbb{X}\) into \(k\) bins \({B_1,...,B_k}\), where each bin \(B_j\) is a cube with sides of length \(h \in (0,1)\) such that \(k = 1/h^r\) is an integer. We denote by \(\hat{f}_k(x)\) the histogram estimator for the confidential data \(\mathbf{X}\), defined as \[\hat{f}_k(x) := \sum_{j=1}^k \dfrac{\hat{p}_j}{h^r} \mathbb{1}_{B_j}(x),\] where \(\hat{p}_j = C_j/n\) and \(C_j = \sum_{i=1}^n \mathbb{1}_{B_j}(X_i)\).

(1) Smoothed estimator mechanism, [8] The histogram estimator can be smoothed in the following way: \[\hat{f}_{k,\sigma}(x) = (1 - \sigma) \hat{f}_{k}(x) + \sigma,\] where \(\sigma \in (0,1)\). Sampling from the smoothed histogram satisfies \(\varepsilon\)-differential privacy if \[\label{smoothedDP} m \log \left ( \dfrac{(1 - \sigma)k}{n\sigma} + 1 \right ) \leq \varepsilon.\tag{17}\]

(2) Perturbed histogram estimator, [8] One can instead perturb the set of counts by adding noise, build a new histogram estimator based on the perturbed counts and then release data sampling from it. Formally, let \(D_j = C_j + \nu_j\), where \(\nu_1,...,\nu_m \stackrel{\scriptsize iid}{\sim}\text{Laplace}(0,2/\varepsilon)\). Let \(\tilde{D}_j = \max\{D_j,0\}\), \(\hat{q}_j = \tilde{D}_j/\sum_{s=1}^k \tilde{D}_s\) for \(j=1,...,k\) and define \[\tilde{f}(x) := \sum_{j=1}^k \dfrac{\hat{q}_j}{h^r} \mathbb{1}_{B_j}(x).\] Any sample from \(\tilde{f}(x)\) preserves \(\varepsilon\)-differential privacy for any \(k\).

(3) Dirichlet-Multinomial mechanism, [9] Let \(\mathbf{p} := (p_1,...,p_k)\) be the vector of probabilities \(p_j := \mathbb{P}[X_i \in B_j]\) for \(j =1,...,k\), and \((C_1,...,C_k)\) the bin counts. The mechanism relies on the following Bayesian parametric model: \[\begin{align} \mathbf{p}\sim\text{Dirichlet}(\alpha_1,...,\alpha_k)\\ C_1,...,C_k|\mathbf{p}\sim\text{Multinomial(n,\mathbf{p})}. \end{align}\] The mechanism involves drawing a vector of probabilities \(\mathbf{q}:= (q_1,...,q_k)\) from the posterior of the model, which is still a Dirichlet with updated parameters \((\alpha_1 + C_1,..., \alpha_k + C_k)\), and generating a synthetic vector of bin counts \(\mathbf{D} := (D_1,...,D_k)\) sampling from a Multinomial\((m,\mathbf{q})\). Such mechanism satisfies \(\varepsilon\)-differential privacy if \[\label{dm95cond} \alpha_j \geq m / (e^\varepsilon - 1)\text{ for all } j=1,...,k.\tag{18}\]

6.3 Rate of convergence in Wasserstein distance of the empirical measure↩︎

We assume \(X_1,...,X_n \stackrel{\scriptsize iid}{\sim}\mathfrak{p}_0\). \(p\)-Wasserstein convergence of the empirical measure \(e_n^{(\mathbf{X})}\) to \(\mathfrak{p_0}\) can be quantified by providing a non-asymptotic estimate of the type \[\label{rate95empirical} \varepsilon_{n,p}(\mathbb{X},\mathfrak{p}_0) := \mathbb{E}_{\otimes^n \mathfrak{p}_0}[ \mathcal{W}_p^{\mathcal{P}(\mathbb{X})}(e_n^{(\mathbf{X})}, \mathfrak{p}_0)] \leq g(n)\tag{19}\] for all \(n \geq 1\), where \(g\) is a suitable function. The following theorem provides such an estimate in the case \(\mathbb{X} \subseteq \mathbb{R}^d\).

If \(\mathfrak{p}_0\) ha sufficiently many moments, then the term \(n^{-(q-p)/q}\) is small and can be neglected. We need this result when proving Theorems 3 and 4, where we have to provide rates for the expected 1-Wasserstein distance between the empirical measure of the synthetic data and the data generating distribution.

6.4 Bayesian consistency↩︎

To prove consistency in the Dirichlet-Multinomial subcase we need the following result, arising from the theory of Bayesian consistency and posterior contraction rates ([36]). Being in the case of Bayesian parametric models, consider the metric space \((\Theta, d_{\Theta})\), where \(\Theta\) is the parameter space. We denote \(\mathcal{W}_p^{\mathcal{P}(\Theta)}(\cdot , \cdot )\) the \(p\)-Wasserstein distance defined in \((\Theta, d_{\theta})\), assuming it is a complete and separable metric space.

Let \(X_1,..., X_n\) be a sequence of categorical random variables taking values in the finite set \(\{a_1,...,a_k\} \subset \mathbb{X}\). The parameter space \(\Theta\), in this case, coincides with the interior of the \(k-1\) dimensional simplex \[\mathscr{S}^{k-1} = \{ (\theta_1,...,\theta_{k-1}) \in [0,1]^{k-1} : \sum_{i=1}^{k-1} \theta_i \leq 1 \}.\]

Notice that the above proposition holds assuming a Dirichlet prior with parameters \((\alpha_1,...,\alpha_k)\) such that \(\alpha_i \geq 2\) for all \(i=1,...,k\).

6.5 Lipschitz continuity of the Dirichlet-Multinomial operator↩︎

We state and prove a result, needed in the proof of Theorem 3, concerning a property of the operator \(\mathscr{T} : (\Theta, d_{\Theta}) \rightarrow (\mathcal{P} (\mathbb{X}),\mathcal{W}_1^{\mathcal{P}(\mathbb{X})})\), which for a Dirichlet-Multinomial model is defined as \[\mathscr{T}(\theta) = \sum_{i=1}^k \theta_i \delta_{a_i}\] for all \(\theta \in \Theta \equiv \mathscr{S}^{k-1}\), where \(\theta_k := 1 - \theta_1 - \cdots - \theta_{k-1}\). We assume \(d_{\Theta}\) equal to the metric induced by the \(l^2\) norm in \(\mathbb{R}^{k-1}\).

7 Proofs↩︎

7.1 Proof of Theorem 1↩︎

By Proposition 2, it is enough to prove instance-level \((\varepsilon,\delta)\)-probabilistic differential privacy. Work under the fixed-dataset notation introduced above. For ease of notation let \(K = K_m^{(n)}\). Fix a neighbouring dataset \(\tilde{\mathbf{x}}\) such that \(h(\mathbf{x},\tilde{\mathbf{x}})=1\). By exchangeability, assume that the datasets differ only in the first coordinate: \[x_1=x_l^*, \qquad \tilde{x}_1=b\neq x_l^*, \qquad x_i=\tilde{x}_i,\quad i=2,\ldots,n.\] We write \(q_{\mathbf{x}}\) and \(q_{\tilde{\mathbf{x}}}\) for densities of \(Q_{\mathbf{x}}\) and \(Q_{\tilde{\mathbf{x}}}\) with respect to a common dominating measure. Define \[A_{\mathbf{x},\tilde{\mathbf{x}}} := \left\{ z\in \mathbb{X}^m: q_{\mathbf{x}}(z)\le e^\varepsilon q_{\tilde{\mathbf{x}}}(z) \right\}.\] We now control \[Q_{\mathbf{x}}(A_{\mathbf{x},\tilde{\mathbf{x}}}^c)\] for the two possible types of value \(b\).

7.1.0.1 Case 1: \(b\) is already present in \(\mathbf{x}\).

Assume \[b=x_t^* \qquad\text{for some }t\neq l.\]

First suppose that \(n_l\ge 2\). Then \(x_l^*\) remains an old species under \(\tilde{\mathbf{x}}\), with frequency \(n_l-1\), while \(x_t^*\) has frequency \(n_t+1\). The number of old species is the same under \(\mathbf{x}\) and \(\tilde{\mathbf{x}}\). Using the posterior-predictive density induced by the Pitman–Yor EPPF, we obtain \[\frac{q_{\mathbf{x}}(z)}{q_{\tilde{\mathbf{x}}}(z)} = \frac{(n_t-\sigma)_{S_t}}{(n_t+1-\sigma)_{S_t}} \frac{(n_l-\sigma)_{S_l}}{(n_l-1-\sigma)_{S_l}}.\] Equivalently, \[\frac{q_{\mathbf{x}}(z)}{q_{\tilde{\mathbf{x}}}(z)} = \frac{n_t-\sigma}{n_t+S_t-\sigma} \frac{n_l+S_l-1-\sigma}{n_l-1-\sigma}.\] Therefore, in this subcase, \[A_{\mathbf{x},\tilde{\mathbf{x}}}^c \subseteq \left\{ \frac{n_t-\sigma}{n_t+S_t-\sigma} \frac{n_l+S_l-1-\sigma}{n_l-1-\sigma} > e^\varepsilon \right\}.\]

Now suppose instead that \(n_l=1\). Then the value \(x_l^*\) disappears from \(\tilde{\mathbf{x}}\). Hence, under \(Q_{\tilde{\mathbf{x}}}\), the fixed value \(x_l^*\) is not an old atom. Since \(H\) is nonatomic, \[Q_{\tilde{\mathbf{x}}} \left( \exists r\le m: Z_r=x_l^* \right) = 0.\] Thus the event \[\{S_l\ge 1\}\] is singular for \(Q_{\mathbf{x}}\) with respect to \(Q_{\tilde{\mathbf{x}}}\), and it must be included in the bad privacy event.

On the complementary event \(\{S_l=0\}\), the value \(x_l^*\) is not released. Then the released sample contains the same new species under both \(\mathbf{x}\) and \(\tilde{\mathbf{x}}\), but \(\tilde{\mathbf{x}}\) has one fewer old species. The likelihood ratio becomes \[\frac{q_{\mathbf{x}}(z)}{q_{\tilde{\mathbf{x}}}(z)} = \frac{\theta+(j+K-1)\sigma}{\theta+(j-1)\sigma} \frac{n_t-\sigma}{n_t+S_t-\sigma}.\] Consequently, when \(n_l=1\), \[A_{\mathbf{x},\tilde{\mathbf{x}}}^c \subseteq \{S_l\ge 1\} \cup \left( \{S_l=0\} \cap \left\{ \frac{\theta+(j+K-1)\sigma}{\theta+(j-1)\sigma} \frac{n_t-\sigma}{n_t+S_t-\sigma} > e^\varepsilon \right\} \right).\]

7.1.0.2 Case 2: \(b\) is not present in \(\mathbf{x}\).

Assume \[b\notin\{x_1^*,\ldots,x_j^*\}.\] Let \[E_b:=\{\exists r\le m: Z_r=b\}.\] Since \(b\) is fixed before generating \(Z\), and since \(H\) is nonatomic, \[Q_{\mathbf{x}}(E_b)=0.\] Thus we may work on \(E_b^c\), up to a \(Q_{\mathbf{x}}\)-null event.

First suppose that \(n_l\ge 2\). Then \(x_l^*\) remains an old species under \(\tilde{\mathbf{x}}\), with frequency \(n_l-1\), and \(b\) is an old singleton under \(\tilde{\mathbf{x}}\) with released count zero on \(E_b^c\). The likelihood ratio is \[\frac{q_{\mathbf{x}}(z)}{q_{\tilde{\mathbf{x}}}(z)} = \frac{\theta+j\sigma}{\theta+(j+K)\sigma} \frac{(n_l-\sigma)_{S_l}}{(n_l-1-\sigma)_{S_l}}.\] Equivalently, \[\frac{q_{\mathbf{x}}(z)}{q_{\tilde{\mathbf{x}}}(z)} = \frac{\theta+j\sigma}{\theta+(j+K)\sigma} \frac{n_l+S_l-1-\sigma}{n_l-1-\sigma}.\] Hence, since \(Q_{\mathbf{x}}(E_b)=0\), \[Q_{\mathbf{x}}(A_{\mathbf{x},\tilde{\mathbf{x}}}^c) \le Q_{\mathbf{x}} \left( \frac{\theta+j\sigma}{\theta+(j+K)\sigma} \frac{n_l+S_l-1-\sigma}{n_l-1-\sigma} > e^\varepsilon \right).\]

Now suppose that \(n_l=1\). Then \(\tilde{\mathbf{x}}\) is obtained by replacing the singleton old species \(x_l^*\) by the singleton old species \(b\). On the event \(\{S_l\ge 1\}\), the released sample contains \(x_l^*\), which is not an old atom under \(\tilde{\mathbf{x}}\). Since \(H\) is nonatomic, \[Q_{\tilde{\mathbf{x}}}(S_l\ge 1)=0.\] Thus \(\{S_l\ge 1\}\) is again singular.

On the event \[\{S_l=0\}\cap E_b^c,\] neither \(x_l^*\) nor \(b\) appears in the released sample. The two datasets then differ only by the label of an old singleton with released count zero. The old-species contribution is \[(1-\sigma)_0=(1-\sigma)_0=1,\] the number of old species is \(j\) for both datasets, and the new synthetic species are the same under both descriptions. Therefore \[\frac{q_{\mathbf{x}}(z)}{q_{\tilde{\mathbf{x}}}(z)} = 1 \qquad \text{on } \{S_l=0\}\cap E_b^c.\] Since \(Q_{\mathbf{x}}(E_b)=0\), we conclude that, in this subcase, \[Q_{\mathbf{x}}(A_{\mathbf{x},\tilde{\mathbf{x}}}^c) \le Q_{\mathbf{x}}(S_l\ge 1).\]

Then, the exact pairwise bad events are: \[\mathcal{E}_{l,t}^{\mathrm{old}}(\varepsilon) := \begin{cases} \left\{ \dfrac{n_t-\sigma}{n_t+S_t-\sigma} \dfrac{n_l+S_l-1-\sigma}{n_l-1-\sigma} > e^\varepsilon \right\}, & n_l\ge 2, \\ \{S_l\ge 1\} \cup \left( \{S_l=0\} \cap \left\{ \dfrac{\theta+(j+K-1)\sigma}{\theta+(j-1)\sigma} \dfrac{n_t-\sigma}{n_t+S_t-\sigma} > e^\varepsilon \right\} \right), & n_l=1, \end{cases}\] for neighbors changing \(x^*_l\) into an already observed \(x^*_t\), and \[\mathcal{E}_l^{\mathrm{new}}(\varepsilon) := \begin{cases} \left\{ \dfrac{\theta+j\sigma}{\theta+(j+K)\sigma} \dfrac{n_l+S_l-1-\sigma}{n_l-1-\sigma} > e^\varepsilon \right\}, & n_l\ge 2, \\ \{S_l\ge 1\}, & n_l=1, \end{cases}\] for neighbors changing \(x^*_l\) into a value not already present in \(\mathbf{x}\).

Thus, \[\tilde{\delta}(\varepsilon,\mathbf{x}) := \max\left\{ \max_{1\le l\le j} Q_{\mathbf{x}}\left(\mathcal{E}_l^{\mathrm{new}}(\varepsilon)\right), \max_{\substack{1\le l,t\le j\\ t\neq l}} Q_{\mathbf{x}}\left(\mathcal{E}_{l,t}^{\mathrm{old}}(\varepsilon)\right) \right\},\]

7.2 Proof of Corollary 1↩︎

Set \(\sigma=0\) in Theorem 1. If \(n_l\ge2\), the bad event for changing \(x_l^*\) into a new value is \[\left\{ \frac{n_l+S_l-1}{n_l-1}>e^\varepsilon \right\} = \left\{ S_l>(e^\varepsilon-1)(n_l-1) \right\} = \left\{ S_l\ge k_l(\varepsilon) \right\}.\] The bad event for changing \(x_l^*\) into an old value is contained in the same event, since \(n_t/(n_t+S_t)\le1\). If \(n_l=1\), both old-value and new-value changes reduce to the singular event \(\{S_l\ge1\}=\{S_l\ge k_l(\varepsilon)\}\), because the remaining likelihood-ratio condition in the old-value case is bounded by \(1<e^\varepsilon\). Hence Theorem 1 applies with \[\max_{1\le i\le j} Q_{\mathbf{x}}\left(S_i\ge k_i(\varepsilon)\right)\] in place of \(\delta^\sharp(\varepsilon,\mathbf{x})\). Under the Dirichlet posterior-predictive distribution, conditionally on \(K_n=j\) and \(\mathbf{N}_n=\mathbf{n}\), \[S_i \sim \mathrm{BetaBin}\left(m,n_i,\theta+n-n_i\right).\] Therefore \[Q_{\mathbf{x}}\left(S_i\ge k_i(\varepsilon)\right) = \sum_{s=k_i(\varepsilon)}^m \binom ms \frac{ (n_i)_s (\theta+n-n_i)_{m-s} }{ (\theta+n)_m },\] which gives the stated \(\delta^\sharp_0(\varepsilon,\mathbf{x})\).

7.3 Proof of Theorem 2↩︎

By the proof of Corollary 1, for the fixed dataset \(\mathbf{x}\), the mechanism satisfies instance-level \((\varepsilon,\delta)\)-differential privacy for every \[\delta> \delta^\sharp_0(\varepsilon,\mathbf{x}) = \max_{1\le i\le j} Q_{\mathbf{x}} \left( S_i\ge k_i(\varepsilon) \right),\] Moreover, conditionally on \(K_n=j\) and \(\mathbf{N}_n=\mathbf{n}\), \[S_i \sim \mathrm{BetaBin} \left( m, n_i, \theta+n-n_i \right).\]

Therefore the instance-level privacy parameter depends on \(\mathbf{x}\) only through the multiplicities \(n_i\). For \(r=1,\ldots,n\), let \[Y_{r,n,m}\sim \mathrm{BetaBin} \left( m, r, \theta+n-r \right),\] and set \[\delta^{\mathrm G}_{n,m}(\varepsilon) := \max_{1\le r\le n} \mathbb{P} \left( Y_{r,n,m}\ge k(r, \varepsilon) \right),\] where \(k(r, \varepsilon)\) is as in 8 . Then, for every dataset \(\mathbf{x}\), \(\delta^\sharp_0(\varepsilon,\mathbf{x}) \le \delta^{\mathrm G}_{n,m}(\varepsilon)\). Since \(\mathbf{x}\) was arbitrary, the instance-level guarantee holds uniformly over all datasets. Hence, for every pair \(\mathbf{x},\tilde{\mathbf{x}}\in\mathcal{X}^n\) with \(h(\mathbf{x},\tilde{\mathbf{x}})=1\), and every measurable \(B\in\mathcal{X}^m\), \[Q_{\mathbf{x}}(B) \le e^\varepsilon Q_{\tilde{\mathbf{x}}}(B) + \delta\] for every \[\delta>\delta^{\mathrm G}_{n,m}(\varepsilon).\] Thus the mechanism satisfies global \((\varepsilon,\delta)\)-differential privacy for every \[\delta\in[0,1) \quad\text{such that}\quad \delta>\delta^{\mathrm G}_{n,m}(\varepsilon).\]

It remains to express and upper bound \(\delta^{\mathrm G}_{n,m}(\varepsilon)\). Since the beta-binomial probability mass function is \[\mathbb{P}(Y_{r,n,m}=s) = \binom ms \frac{ (r)_s(\theta+n-r)_{m-s} }{ (\theta+n)_m }, \qquad s=0,\ldots,m,\] we have \[\delta^{\mathrm G}_{n,m}(\varepsilon) = \max_{1\le r\le n} \sum_{s=k_r(\varepsilon)}^m \binom ms \frac{ (r)_s(\theta+n-r)_{m-s} }{ (\theta+n)_m },\] with the convention that the sum is zero whenever \(k_r(\varepsilon)>m\).

We now prove the simpler global upper bound. First consider \(r=1\). Then \[\begin{align} \mathbb{P}(Y_{1,n,m}\ge 1) &= 1-\mathbb{P}(Y_{1,n,m}=0) \\ &= 1- \frac{(\theta+n-1)_m}{(\theta+n)_m} \\ &= 1- \frac{\theta+n-1}{\theta+n+m-1} \\ &= \frac{m}{\theta+n+m-1}. \end{align}\] This is the singular singleton contribution.

Now consider \(r\ge2\). Put \[a_\varepsilon:=e^\varepsilon-1.\] By definition, \[k_r(\varepsilon) = \left\lfloor a_\varepsilon(r-1) \right\rfloor+1.\] Since \(Y_{r,n,m}\) is integer-valued, \[\{Y_{r,n,m}\ge k_r(\varepsilon)\} = \{Y_{r,n,m}>a_\varepsilon(r-1)\}.\] Moreover, \[\mathbb{E}[Y_{r,n,m}] = \frac{mr}{\theta+n}.\] Therefore, by Markov’s inequality, \[\begin{align} \mathbb{P} \left( Y_{r,n,m}\ge k_r(\varepsilon) \right) &= \mathbb{P} \left( Y_{r,n,m}>a_\varepsilon(r-1) \right) \\ &\le \frac{ \mathbb{E}[Y_{r,n,m}] }{ a_\varepsilon(r-1) } \\ &= \frac{mr}{(\theta+n)(e^\varepsilon-1)(r-1)} \\ &\le \frac{2m}{(\theta+n)(e^\varepsilon-1)}, \end{align}\] where the last inequality uses \(r/(r-1)\le2\) for \(r\ge2\).

Combining the cases \(r=1\) and \(r\ge2\), we obtain \[\delta^{\mathrm G}_{n,m}(\varepsilon) \le \max\left\{ \frac{m}{\theta+n+m-1}, \frac{2m}{(\theta+n)(e^\varepsilon-1)} \right\}.\] Thus \(\delta^{\mathrm G}_{n,m}(\varepsilon)\le\bar\delta_{n,m}(\varepsilon)\), and every \(\delta>\bar\delta_{n,m}(\varepsilon)\) is admissible. Hence, for fixed \(\theta\) and \(\varepsilon\), \[\bar\delta_{n,m}(\varepsilon) = O\left(\frac{m}{n}\right).\] This completes the proof.

7.4 Proof of Corollary 2↩︎

In this case, the mechanism cannot generate new unique values, because \(z = j\) and \(\theta = z |\sigma |\), with \(\sigma < 0\). Therefore the proof goes as that of Theorem 1, but only Case \(1\) can occur. Moreover, no singularity for \(Q_{\mathbf{x}}\) with respect to \(Q_{\mathbf{\tilde{x}}}\) happens. It follows that to satisfy instance-level \((\varepsilon,\delta)\)-differential privacy it is enough to require \[\label{ddd} \dfrac{n_t + |\sigma|}{n_t + S_t + |\sigma| } \dfrac{n_l + S_l - 1 + |\sigma|}{n_l - 1 + |\sigma|} \leq e^{\varepsilon}\tag{20}\] for all \(t,l=1,...,j\) such that \(t \neq l\). Since \(\sigma\) can take any negative value, we require \(n_i + |\sigma| - 1 \geq m/(e^\varepsilon-1)\) for all \(i=1,...,j\) and (20 ) is satisfied with probability \(1\), i.e. \(\delta = 0\). Thus if \[m \leq (| \sigma | + n_i - 1)(e^\varepsilon - 1)\] holds for all \(i = 1,...,j\), then we have instance-level \(\varepsilon\)-differential privacy.

7.5 Proof of Theorem 3↩︎

The mechanism \(Q_n\) has the following density with respect to the counting measure: \[q_n(\mathbf{z} \,|\,\mathbf{X} = \mathbf{x}) = \int_{\Theta} \left [ \prod_{j=1}^m f_\theta(z_j) \right ] \psi_n( d \theta \,|\,\mathbf{X} = \mathbf{x}),\] where \(f_\theta(z) = \left( \prod_{i=1}^k \theta_i^{\mathbb{1}_{\{a_i\}}(z)} \right) \mathbb{1}_{\{a_1,...,a_k\}}(z)\) is the density of a Multinomial with support \(\{a_1,...,a_k\}\), and \(\psi_n\) is the posterior. Hence, by Fubini-Tonelli’s theorem, we have \[\begin{align} & \mathbb{E}_{\nu_{n,m}}\left [\mathcal{W}_1^{\mathcal{P}(\mathbb{X})}(e_m^{(\mathbf{Z})},\mathfrak{p}_0) \right ] = \int_{\mathbb{X}^m \times \mathbb{X}^n} \mathcal{W}_1^{\mathcal{P}(\mathbb{X})}(e_m^{(\mathbf{z})},\mathfrak{p}_0) \;q_n(\mathbf{z} \,|\,\mathbf{X} = \mathbf{x}) \;d\mathbf{z} \;\mathfrak{p}_0^n(d\mathbf{x}) = \\ & \int_{\mathbb{X}^m \times \mathbb{X}^n} \left ( \int_{\Theta} \mathcal{W}_1^{\mathcal{P}(\mathbb{X})}(e_m^{(\mathbf{z})},\mathfrak{p}_0) \left [ \prod_{j=1}^m f_\theta(z_j) \right ] \psi_n( d \theta \,|\,\mathbf{X} = \mathbf{x}) \right ) d\mathbf{z} \;\mathfrak{p}_0^n(d\mathbf{x}) = \\ & \int_{\Theta \times \mathbb{X}^n } \left ( \int_{\mathbb{X}^m} \mathcal{W}_1^{\mathcal{P}(\mathbb{X})}(e_m^{(\mathbf{z})},\mathfrak{p}_0) \left [ \prod_{j=1}^m f_\theta(z_j) \right ] d\mathbf{z} \right ) \psi_n( d \theta \,|\,\mathbf{X} = \mathbf{x}) \;\mathfrak{p}_0^n(d\mathbf{x}) = \\ &\mathbb{E}_{\psi_n \otimes \mathfrak{p}_0^n} \left [\mathbb{E} \left [ \mathcal{W}_1^{\mathcal{P}(\mathbb{X})}(e_m^{(\mathbf{Z})},\mathfrak{p}_0) \,|\,\theta \right ] \right ]. \end{align}\] By triangular inequality, we have \[\mathbb{E}_{\psi_n \otimes \mathfrak{p}_0^n} \left [\mathbb{E} \left [ \mathcal{W}_1^{\mathcal{P}(\mathbb{X})}(e_m^{(\mathbf{Z})},\mathfrak{p}_0) \,|\,\theta \right ] \right ] \leq \mathbb{E}_{\psi_n \otimes \mathfrak{p}_0^n} \left [\mathbb{E} \left [ \mathcal{W}_1^{\mathcal{P}(\mathbb{X})}(e_m^{(\mathbf{Z})},\mathscr{T}(\theta)) \,|\,\theta \right ] \right ] + \mathbb{E}_{\psi_n \otimes \mathfrak{p}_0^n} \left [\mathbb{E} \left [ \mathcal{W}_1^{\mathcal{P}(\mathbb{X})}(\mathscr{T}(\theta),\mathfrak{p}_0) \,|\,\theta \right ] \right ].\] By the property of the conditional expectation \[\mathbb{E}_{\psi_n \otimes \mathfrak{p}_0^n} \left [\mathbb{E} \left [ \mathcal{W}_1^{\mathcal{P}(\mathbb{X})}(\mathscr{T}(\theta),\mathfrak{p}_0) \,|\,\theta \right ] \right ] = \mathbb{E}_{\psi_n \otimes \mathfrak{p}_0^n} \left [\mathcal{W}_1^{\mathcal{P}(\mathbb{X})}(\mathscr{T}(\theta),\mathfrak{p}_0) \right ].\] We can write \[\mathbb{E}_{\psi_n \otimes \mathfrak{p}_0^n} \left [\mathcal{W}_1^{\mathcal{P}(\mathbb{X})}(\mathscr{T}(\theta),\mathfrak{p}_0) \right ] = \mathbb{E}_{\mathfrak{p}_0^n} \left [\int_{\Theta^2} \mathcal{W}_1^{\mathcal{P}(\mathbb{X})}(\mathscr{T}(\theta),\mathscr{T}(\phi)) \;\psi_n(d \theta | \mathbf{X} = \mathbf{x}) \;\delta_{\theta_0}(d \phi) \right ].\] By Lemma 2 and Hölder’s inequality, we obtain \[\begin{align} & \mathbb{E}_{ \otimes^n \mathfrak{p}_0} \left [\int_{\Theta^2} \mathcal{W}_1^{\mathcal{P}(\mathbb{X})}(\mathscr{T}(\theta),\mathscr{T}(\phi)) \;\psi_n(d \theta \,|\,\mathbf{X} = \mathbf{x}) \;\delta_{\theta_0}(d \phi) \right ] \leq \\ & D \sqrt{k-1} \;\mathbb{E}_{\otimes^n \mathfrak{p}_0} \left [\int_{\Theta^2} \lVert \theta - \phi \rVert_{l^2} \;\psi_n(d \theta | \mathbf{X} = \mathbf{x}) \;\delta_{\theta_0}(d \phi) \right ] \leq \\ & D \sqrt{k-1} \;\mathbb{E}_{\otimes^n \mathfrak{p}_0} \left [ \left ( \int_{\Theta^2} \lVert \theta - \phi \rVert_{l^2}^2 \;\psi_n(d \theta | \mathbf{X} = \mathbf{x}) \;\delta_{\theta_0}(d \phi) \right )^{1/2} \right ] = \\ & D\sqrt{k-1}\mathbb{E}_{\otimes^n \mathfrak{p}_0} \left[ \mathcal{W}_2^{\mathcal{P}(\Theta)}(\psi_n( \;\cdot \,|\,\mathbf{X}), \delta_{\theta_0}) \right] = O(n^{-1/2}), \end{align}\] where the last equality is due to Proposition 2. Moreover, by Theorem 5, we have \[\mathbb{E}_{\psi_n \otimes \mathfrak{p}_0^n} \Bigl[ \mathbb{E} \bigl[ \mathcal{W}_1^{\mathcal{P}(\mathbb{X})}(e_m^{(\mathbf{Z})}, \mathscr{T}(\theta)) \,|\,\theta \bigr] \Bigr] = \begin{cases} O(m^{-1/2}) & \text{if } d < 2, \\[1mm] O(m^{-1/2} \log(1+m)) & \text{if } d = 2, \\[1mm] O(m^{-1/d}) & \text{if } d > 2. \end{cases}\]

since \(Z_1,...,Z_m \,|\,\theta \stackrel{\scriptsize iid}{\sim}\mathscr{T}(\theta)\) and a discrete measure with finite support has \(q\)-moments finite for all \(q \geq 1\).

7.6 Proof of Lemma 1↩︎

We use a dyadic transport technique as in [39], which allows to compute the order of \(\mathbb{E}_{\tilde{p}|X^{\left( n\right) }}\left( \mathcal{W}_1\left( P,H_{n}\right) \right)\), where \(X^{(n)}=(X_1,\dots,X_n)\) and \(P\) is a random measure distributed as \(\tilde{p} |X^{(n)}\), which has distribution \(\pi _{n}\left( \cdot |X^{\left( n\right) }\right) =\mathscr{D}\left( \theta +n,H_n\right)\).. Consider a dyadic partition \(\left\{ \mathcal{Q}^{k}\right\} _{k=1}^{k^{\ast }}\) of \(\mathbb{X}\) with parameter \(\delta <1\): then Proposition 1 from [39] gives the inequality\[\mathcal{W}_{1}\left( P,H_{n}\right) \leq \delta ^{k^{\ast }}+\sum_{k=1}^{k^{\ast }}\delta ^{k-1}\sum_{Q_{i}^{k}\in \mathcal{Q}^{k}}\left\vert P\left( Q_{i}^{k}\right) -H_{n}\left( Q_{i}^{k}\right) \right\vert ,\]

and notice we have \(\sum_{Q_{i}^{k}\in \mathcal{Q}^{k}}\left\vert P\left( Q_{i}^{k}\right) -H_{n}\left( Q_{i}^{k}\right) \right\vert =\left\vert \left\vert \mathbf{P}^{k}-\mathbf{H}_{n}^{k}\right\vert \right\vert _{1}\), where \(\mathbf{P}^{k}= \left(P\left( Q_{1}^{k}\right) ,...,P\left( Q_{m_{k}}^{k}\right) \right)\), \(\mathbf{H}_{n}^{k}=\left( H_{n}\left( Q_{1}^{k}\right) ,...,H_{n}\left( Q_{m_{k}}^{k}\right) \right)\) and \(m_{k}\) is the cardinality of the partition \(\mathcal{Q}^{k}\). Hence\[\label{weedineq} \mathcal{W}_{1}\left( P,H_{n}\right) \leq \delta ^{k^{\ast }}+\sum_{k=1}^{k^{\ast }}\delta ^{k-1}\left\vert \left\vert \mathbf{P}^{k}-\mathbf{H}_{n}^{k}\right\vert \right\vert_{1} .\tag{21}\]

\(\mathbf{P}^{k}\) is known to be, conditionally on \(X^{\left( n\right) }\), a random vector with Dirichlet distribution, whose mean is the vector \(H_{n}^{k}\).

If one considers a random vector \(\mathbf{Y}\sim \text{Dirichlet}\left( \beta _{1},...,\beta _{n}\right)\), defining \(\mu _{i}=\frac{\beta _{i}}{\sum \beta _{i}}=\frac{\beta _{i}}{\beta _{\cdot }}\) for \(i=1,...n\), then \[\begin{align} \mathbb{E}\left( \left\vert \left\vert \mathbf{Y-\mu }\right\vert \right\vert _{1}\right) &\leq \sqrt{n}\sqrt{\mathbb{E}\left( \left\vert \left\vert \mathbf{Y-\mu }\right\vert \right\vert _{2}^{2}\right) }=\sqrt{n}\sqrt{\sum_{i=1}^{n}var\left( Y_{i}\right) }\\ &=\sqrt{n}\sqrt{\sum_{i=1}^{n}\frac{\mu _{i}\left( 1-\mu _{i}\right) }{\beta _{\cdot }+1}}=\sqrt{n}\sqrt{\frac{1}{\beta _{\cdot }+1}\left( 1-\sum \mu _{i}^{2}\right) }\leq \sqrt{n}\frac{1}{\sqrt{\beta _{\cdot }+1}}. \end{align}\]

So in our case \(\mathbb{E}_{\tilde{p}|X^{n}}\left( \left\vert \left\vert \mathbf{P}^{k}-\mathbf{H}_{n}^{k}\right\vert \right\vert _{1}\right) \leq \sqrt{\frac{m_{k}}{\theta +n+1}}\), and then taking the expectation of both sides in (21 ) yields\[\mathbb{E}_{\tilde{p}|X^{n}}\left(\mathcal{W}_{1}\left( P,H_{n}\right) \right) \leq \delta ^{k^{\ast }}+\sum_{k=1}^{k^{\ast }}\delta ^{k-1}\mathbb{E}_{\tilde{p}|X^{n}}\left( \left\vert \left\vert \mathbf{P}^{k}-\mathbf{H}_{n}^{k}\right\vert \right\vert _{1}\right) \leq \delta ^{k^{\ast }}+\frac{1}{\sqrt{\theta +n+1}}\sum_{k=0}^{k^{\ast }-1}\delta ^{k}\sqrt{m_{k}}.\]

Since we have that if \(Q\in \mathcal{Q}^{k}\) then \(\text{diam}\left( Q\right) \leq \delta ^{k}\), it holds \(m_{k}=O\left( \delta ^{-kd}\right)\). Then the previous inequality reads \[\mathbb{E}_{\tilde{p}|X^{n}}\left( \mathcal{W}_{1}\left( P,H_{n}\right) \right) \lesssim \delta ^{k^{\ast }}+\frac{1}{\sqrt{\theta +n+1}}\sum_{k=0}^{k^{\ast }-1}\delta ^{k}\delta ^{-\frac{kd}{2}}=\delta ^{k^{\ast }}+\frac{1}{\sqrt{\theta +n+1}}\sum_{k=0}^{k^{\ast }-1}\delta ^{k\left( 1-\frac{d}{2}\right) }.\]

If \(d>2\), using \(\sum_{k=0}^{k^{\ast }-1}\left( \delta ^{1-d/2}\right) ^{k}=\frac{\left( \delta ^{1-d/2}\right) ^{k^{\ast }}-1}{\delta ^{1-d/2}-1}\) yields the inequality \[\mathbb{E}_{\tilde{p}|X^{n}}\left( \mathcal{W}_{1}\left( P,H_{n}\right) \right) \lesssim \delta ^{k^{\ast }}+\frac{1}{\sqrt{\theta +n+1}}\frac{\left( \delta ^{1-d/2}\right) ^{k^{\ast }}-1}{\delta ^{1-d/2}-1}.\]

This holds for any integer \(k^{\ast }\) and \(\delta >0\), so we can optimize the bound. If we take \(\delta\) fixed and optimize in \(t:=\delta ^{k^{\ast }}\), then\[\mathbb{E}_{\tilde{p}|X^{n}}\left( \mathcal{W}_{1}\left( P,H_{n}\right) \right) \lesssim t+\frac{1}{\sqrt{\theta +n}}t^{1-d/2}\]

and the optimization yields \(t^{\frac{d}{2}}=C^{\prime }\frac{1}{\sqrt{\theta +n}}\), i.e. \(t=C^{\prime }\left( \theta +n\right) ^{-\frac{1}{d}}\). This entails that \(\mathbb{E}_{\tilde{p}|X^{n}}\left( \mathcal{W}_{1}\left( P,H_{n}\right) \right) =O\left( n^{-\frac{1}{d}}\right)\).

If \(d=2\),\[\mathbb{E}_{\tilde{p}|X^{n}}\left( \mathcal{W}_{1}\left( P,H_{n}\right) \right) \lesssim \delta ^{k^{\ast }}+\frac{k^{\ast }}{\sqrt{\theta +n+1}}.\]

Optimization in \(k^{\ast }\) gives \(\delta ^{k^{\ast }}\log \delta +\frac{1}{\sqrt{\theta +n+1}}=0\), i.e. \(\delta ^{k^{\ast }}=-\frac{1}{\log \delta }\frac{1}{\sqrt{\theta +n+1}}\), so that \(k^{\ast }=O\left( \log n\right)\) and \(\mathbb{E}_{\tilde{p}|X^{n}}\left( \mathcal{W}_{1}\left( P,H_{n}\right) \right) =O\left( \frac{\log n}{\sqrt{n}}\right)\).

If \(d<2\), \[\mathbb{E}_{\tilde{p}|X^{n}}\left( \mathcal{W}_{1}\left( P,H_{n}\right) \right) \lesssim \delta ^{k^{\ast }}+\frac{1}{\sqrt{\theta +n+1}}\frac{\left( \delta ^{1-d/2}\right) ^{k^{\ast }}-1}{\delta ^{1-d/2}-1}\leq \delta ^{k^{\ast }}+c\frac{1}{\sqrt{\theta +n+1}},\]

so the optimal order is obtained for \(\delta ^{k^{\ast }}=O\left( \frac{1}{\sqrt{n}}\right)\).

In all three optimization procedures, ensuring that \(k^{\ast }\) is integer by taking the ceiling or floor function does not affect the order of convergence.

7.7 Proof of Theorem 4↩︎

If \(f:\mathbb{X}^{m}\rightarrow \lbrack 0,+\infty )\) is measurable, then, by definition of \(\nu _{n,m}\), \[\label{firsteq} \begin{align} \mathbb{E}_{\nu _{n,m}}\left( f\left( \mathbf{Z}\right) \right) &=\int_{\mathbb{X}^{m}\times \mathbb{X}^{n}}f\left( z_{1},...,z_{m}\right) Q_{n}\left( dz_{1},...,dz_{m}|\mathbf{X=x}\right) \mathfrak{p}_{0}^{n}\left( d\mathbf{x}\right) \\ &=\int_{\mathbb{X}^{m}\times \mathbb{X}^{n}}f\left( z_{1},...,z_{m}\right) \left( \int_{\mathcal{P}\left( \mathbb{X}\right) }\prod_{j=1}^{m}\tilde{p}\left( dz_{j}\right) \pi _{n}\left( d\tilde{p}|\mathbf{x}\right) \right) \mathfrak{p}_{0}^{n}\left( d\mathbf{x}\right) \\ &=\int_{\mathcal{P}\left( \mathbb{X}\right) \times \mathbb{X}^{n}}\left( \int_{\mathbb{X}^{m}}f\left( z_{1},...,z_{m}\right) \prod_{j=1}^{m}\tilde{p}\left( dz_{j}\right) \right) \pi _{n}\left( d\tilde{p}|\mathbf{x}\right) \mathfrak{p}_{0}^{n}\left( d\mathbf{x}\right) \\ &=\int_{\mathcal{P}\left( \mathbb{X}\right) \times \mathbb{X}^{n}}\mathbb{E}\left( f\left( \mathbf{Z}\right) |\tilde{p}\right) \pi _{n}\left( d\tilde{p}|\mathbf{x}\right) \mathfrak{p}_{0}^{n}\left( d\mathbf{x}\right), \end{align}\tag{22}\] where the third equality follows from Fubini-Tonelli’s theorem. Now, applying the equality (22 ) to \(f\left( \mathbf{Z}\right) =\mathcal{W}_{1}\left( e_{m}^{\left( \mathbf{Z}\right) },\mathfrak{p}_0\right)\) and using the triangle inequality on \(\tilde{p}\), we get \[\label{firstrieq} \begin{align} \mathbb{E}_{\nu _{n,m}}\left( \mathcal{W}_{1} \left( e_{m}^{\left( \mathbf{Z}\right) },\mathfrak{p}_{0}\right)\right) \leq\;&\underbrace{\int_{\mathcal{P}\left( \mathbb{X}\right) \times \mathbb{X}^{n}} \mathbb{E}\left( \mathcal{W}_{1} \left( e_{m}^{\left( \mathbf{Z}\right) },\tilde{p}\right) \,|\,\tilde{p}\right) \pi _{n}\left( d\tilde{p}\,|\,\mathbf{x}\right)\mathfrak{p}_{0}^{n}\left( d\mathbf{x}\right)}_{A} \\ &\quad+\underbrace{\int_{\mathcal{P}\left( \mathbb{X}\right) \times \mathbb{X}^{n}} \mathbb{E}\left( \mathcal{W}_{1} \left( \tilde{p},\mathfrak{p}_{0}\right) \,|\,\tilde{p}\right) \pi _{n}\left( d\tilde{p}\,|\,\mathbf{x}\right) \mathfrak{p}_{0}^{n}\left( d\mathbf{x}\right)}_{B}. \end{align}\tag{23}\]

We bound separately \(A\) and \(B\).

\(A\), which we define as \(\varepsilon _{m,1}\left( \mathbb{X}\right)\), is the rate of convergence for the mean of the 1-Wasserstein distance between \(e_{m}^{\left( \mathbf{Z}\right) }\) and a random probability measure with law \(\pi _{n}\), posterior of a sample from the Dirichlet prior (up to the integral with respect to \(\mathfrak{p}_{0}^{n}\left( d\mathbf{x}\right)\), which does not change the rate). If we show that a random probability measure distributed as the posterior of a Bayesian model with Dirichlet process prior has \(q\)-moments finite for some integer \(q > 1\), at least \(\pi_n\)-almost surely, applying Theorem 5 under the assumption \(\mathbb{X}\subseteq \mathbb{R}^d\) we get the second part of the thesis. By Proposition 1, \(\tilde{p} \sim \pi_n( \;\cdot \,|\,X_1,\dots,X_n)\) implies \[\tilde{p} \overset{d}{=} \sum_{i=1}^j W_i \delta_{X_i^*} + R_j F_j,\] where \((W_1,...,W_j,R_j) \sim \text{Dirichlet}(n_1,...,n_j, \theta)\), independently of the random distribution \(F_j\), which has \(\mathscr{D}(\theta,H)\) distribution. Moreover, by stick-breaking construction of the DP (definition of Pitman–Yor process with \(\sigma = 0\)), we have \[F_j = \sum_{i=1}^\infty Y_i \delta_{\Phi_i},\] where \(\Phi_i \stackrel{\scriptsize iid}{\sim}H\), and \[Y_1 = V_1, \quad Y_l = V_l \prod_{j = 1}^{l-1} (1 - V_j), \quad l \geq 2,\] with \(\{V_i\}_{i \geq 1}\) sequence of independent random variables taking values in \([0,1]\) and distributed as a \(\text{Beta}(1,\theta)\). The following holds: \[\int_{\mathbb{X}} |x|^q \;\tilde{p}(d x) = \sum_{i=1}^j W_i |X_i^*|^q + R_j \sum_{i = 1}^\infty Y_i |\Phi_i|^q \leq 2 R^q, \qquad \pi_n\text{-a.s.}\] where \(R > 0\) is the radius of the ball that contains the space \(\mathbb{X}\), which exists because \(\mathbb{X}\) is totally bounded. Since we have finite moments for any \(q > 1\), we can neglect the terms involving \(q\) in the bounds of \(\varepsilon_{m,1}(\mathbb{X})\).

Let us turn to \(B\). Since \(\mathbb{E}\left( \mathcal{W}_{1}\left( \tilde{p},\mathfrak{p}_{0}\right) |\tilde{p}\right) =\mathcal{W}_{1}\left( \tilde{p},\mathfrak{p}_{0}\right)\) by conditional determinism, we have \[\begin{align} \int_{\mathcal{P}\left( \mathbb{X}\right) \times \mathbb{X}^{n}}\mathbb{E}\left( \mathcal{W}_{1}\left( \tilde{p},\mathfrak{p}_{0}\right) |\tilde{p}\right) \pi _{n}\left( d\tilde{p}|\mathbf{x}\right) \mathfrak{p}_{0}^{n}\left( d\mathbf{x}\right) &=\int_{\mathcal{P}\left( \mathbb{X}\right) \times \mathbb{X}^{n}}\mathcal{W}_{1}\left( \tilde{p},\mathfrak{p}_{0}\right) \pi _{n}\left( d\tilde{p}|\mathbf{x}\right) \mathfrak{p}_{0}^{n}\left( d\mathbf{x}\right)\\ &=\mathbb{E}_{\mathfrak{p}_{0}^{n}}\left( \mathbb{E}_{\tilde{p}|X^{\left( n\right) }}\left( \mathcal{W}_{1}\left(P,\mathfrak p_0 \right) \right) \right), \end{align}\]

where \(P\) distributed as \(\tilde{p} |X^{(n)} \sim \pi _{n}\left( \cdot |X^{\left( n\right) }\right) =\mathscr{D}\left( \theta +n,H_n\right)\). We have \[\label{secondtrieq} \begin{align} \mathbb{E}_{\mathfrak{p}_{0}^{n}}\left( \mathbb{E}_{\tilde{p}|X^{\left( n\right) }}\left( \mathcal{W}_{1}\left( P,\mathfrak{p}_{0}\right) \right) \right) \leq \mathbb{E}_{\mathfrak{p}_{0}^{n}}\left( \mathcal{W}_{1}\left( \mathfrak{p}_{0},H_{n}\right) \right) +\mathbb{E}_{\mathfrak{p}_{0}^{n}}\left( \mathbb{E}_{\tilde{p}|X^{\left( n\right) }}\left( \mathcal{W}_{1}\left(P,H_{n}\right) \right) \right). \end{align}\tag{24}\]

Concerning the first term on the right hand side of (24 ), convexity of \(\mathcal{W}_{1}\) yields \[\mathcal{W}_{1}^{\;}\left( H_{n},\mathfrak{p}_{0}\right) =\mathcal{W}_{1}^{\; }\left( \frac{\theta }{\theta +n}H+\frac{n}{\theta +n}e_{n}^{\left( \mathbf{X}\right) },\mathfrak{p}_{0}\right) \leq \frac{\theta }{\theta +n}\mathcal{W}_{1}^{\;}\left( H,\mathfrak{p}_{0}\right) +\frac{n}{\theta +n}\mathcal{W} _{1}^{\;}\left( e_{n}^{\left( \mathbf{X}\right) },\mathfrak{p}_{0}\right).\]

\(\mathcal{W}_{1}^{\;}\left( H,\mathfrak{p}_{0}\right)\) is a constant independent on \(n\), and \(\frac{\theta }{\theta +n}=O\left( \frac{1}{n}\right)\). Moreover, Theorem 5 states that \[\mathbb{E}_{\mathfrak{p}_0^n} \Bigl( \mathcal{W}_1 \bigl( e_n^{(\mathbf{X})}, \mathfrak{p}_0 \bigr) \Bigr) = \begin{cases} O(n^{-1/2}) & \text{if } d<2,\\ O(n^{-1/2} \log(1+n)) & \text{if } d=2,\\ O(n^{-1/d}) & \text{if } d>2. \end{cases}\]

It follows that \[\mathbb{E}_{\mathfrak{p}_0^n} \Bigl( \mathcal{W}_1 \bigl( \mathfrak{p}_0, H_n \bigr) \Bigr) = \begin{cases} O(n^{-1/2}) & \text{if } d<2,\\ O(n^{-1/2} \log(1+n)) & \text{if } d=2,\\ O(n^{-1/d}) & \text{if } d>2 \end{cases}\]

A rate for the second term on the right hand side of (24 ) is given by Lemma 1. Summing the two rates we obtain \[\begin{align} \mathbb{E}_{\nu_{n,m}}\left[ \mathcal{W}_1 \left( e_m^{(\mathbf{Z})}, \mathfrak{p}_0 \right) \right] &= \varepsilon_{m,1}(\mathbb{X}) + \begin{cases} O(n^{-1/2}) & \text{if } d<2,\\ O(n^{-1/2} \log(1+n)) & \text{if } d=2,\\ O(n^{-1/d}) & \text{if } d>2, \end{cases} + \begin{cases} O(n^{-1/2}) & \text{if } d<2,\\ O\left(\frac{\log n}{\sqrt{n}}\right) & \text{if } d=2,\\ O(n^{-1/d}) & \text{if } d>2. \end{cases} \\[1mm] &= \begin{cases} O(n^{-1/2}) & \text{if } d<2,\\ O\left(\frac{\log n}{\sqrt{n}}\right) & \text{if } d=2,\\ O(n^{-1/d}) & \text{if } d>2. \end{cases} \end{align}\] This finishes the proof.

Notice that we have been computing a rate for a \(1\)-Wasserstein posterior contraction rate for the Dirichlet prior. Indeed, it holds \[\mathbb{E}_{\mathfrak{p}_{0}^{n}}\left( \mathbb{E}_{\tilde{p}|X^{\left( n\right) }}\left( \mathcal{W}_{1}\left(P,\mathfrak p_0 \right) \right) \right) = \mathbb{E}_{\mathfrak{p}_{0}^{n}}\left( \mathcal{W}_{1}^{\mathcal{P}(\mathcal{P} \left( \mathbb{X})\right) }\left( \pi_{n}\left( \cdot |X^{\left( n\right) }\right) ,\delta _{\mathfrak{p}_{0}}\right) \right)\] because \[\begin{align} \mathcal{W}_{1}^{\mathcal{P}(\mathcal{P}\left( \mathbb{X})\right) }\left( \pi _{n}\left( \cdot |X^{\left( n\right) }\right) ,\delta _{\mathfrak{p}_{0}}\right) &=\inf_{\eta \in \Pi\left( \pi _{n}\left( \cdot |X^{\left( n\right) }\right) ,\delta _{\mathfrak{p}_{0}}\right) }\int_{\mathcal{P}\left( \mathbb{X}\right) \times \mathcal{P}\left( \mathbb{X}\right) }\mathcal{W}_{1}\left( p_{1},p_{2}\right) \eta \left( dp_{1}dp_{2}\right) \\ &=\int_{\mathcal{P}\left( \mathbb{X}\right) }\mathcal{W}_{1}\left( p_{1},\mathfrak{p}_{0}\right) \pi _{n}\left( dp_{1}|X^{\left( n\right) }\right) , \end{align}\] since the only coupling with a delta measure is the independent coupling. Therefore \[\mathbb{E}_{\mathfrak{p}_{0}^{n}}\left( \mathcal{W}_{1}^{\mathcal{P}\left( \mathcal{P}(\mathbb{X})\right) }\left( \pi _{n}\left( \cdot |X^{\left( n\right) }\right) ,\delta _{\mathfrak{p}_{0}}\right) \right) =\int_{\mathbb{X}^{n}}\left( \int_{\mathcal{P}\left( \;\mathbb{X}\right) \;}\mathcal{W}_{1}\left( p_{1},\mathfrak{p}_{0}\right) \pi _{n}\left( dp_{1}|\mathbf{x}\right) \right) \mathfrak{p}_{0}^{n}\left( d\mathbf{x}\right).\]

8 Details on numerical illustrations↩︎

We provide additional details on the experiments in Section 4.1, Section 4.2, and Section 4.3.

8.1 Details on downstream Bayesian inference↩︎

The downstream-inference experiment has two components. The first is a timing sanity check for the exact mechanism-aware posterior associated with the perturbed-histogram synthetic-sample release. In this exact formulation, the MCMC state contains the full latent confidential sample \(X_{1:n}\), together with the noisy histogram variables used internally by the perturbed histogram mechanism. At each saved iteration, posterior inference for \(\tilde{p}\) is performed from the closed-form conditional posterior \[\tilde{p} \,|\,X_1,\ldots,X_n \sim \mathscr D\left(\theta+n,\frac{\theta H+\sum_{i=1}^{n}\delta_{X_i}}{\theta+n}\right).\] For \(n=10^4\), \(m=10^2\), and \(25\) histogram bins, the reference implementation takes about six minutes to obtain \(1000\) posterior samples. This timing is reported only to document the computational scale of the exact posterior. We do not use this sampler in repeated Monte Carlo experiments or in the real-data analysis.

The second component is the repeated fallback experiment reported in Section 4.1. The confidential data are generated from a distribution supported on a regular grid in \([0,1]\). The grid probabilities are obtained by evaluating a two-component beta mixture on the grid and normalizing the resulting weights. This produces a non-uniform discrete distribution with asymmetric shape and non-negligible tail mass. We generate \(n=2000\) confidential observations and compare three downstream workflows over \(20\) independent Monte Carlo replicates.

For the Dirichlet-process posterior-predictive mechanism, we release \(m\) synthetic observations and compute posterior summaries from the ordinary Dirichlet-process posterior given the released sample. For the direct perturbed histogram, the observed object is the noisy histogram output, and the mechanism-aware posterior is explored by MCMC over the latent confidential bin counts. For the direct smoothed histogram, the output is treated as a computational surrogate. As discussed in Section 4.1, this direct smoothed output is not differentially private, except in the degenerate case of complete smoothing, and is therefore included only as a non-private diagnostic.

Table ¿tbl:tab:downstream95summary? summarizes the downstream-inference results. We report bias, root mean square error, average credible-interval length, and empirical coverage for the posterior mean, quartiles, and right-tail probability \(\tilde{p}((0.75,1])\). We also report wall-clock time and effective sample size per second when MCMC is used. The main qualitative conclusion is that the Dirichlet-process posterior-predictive mechanism has statistical accuracy comparable to the histogram-based workflows in this simplified setting, while avoiding mechanism-aware latent-data or latent-count MCMC.

8.2 Details on the convergence simulation↩︎

In Section 4.2, the simulated confidential data are generated as follows. Let \(G\sim\mathrm{Geometric}(0.05)\), with support \(\{1,2,\ldots\}\), and define \(X=T(G)\), where \[T(k)=\frac{2(k-2^{r(k)-1})+1}{2^{r(k)}},\qquad r(k)=\lfloor \log_2 k \rfloor+1.\] This map sends the positive integers to dyadic midpoints in \([0,1]\) by increasing dyadic resolution. In particular, \(1\mapsto 1/2\), \(2\mapsto 1/4\), \(3\mapsto 3/4\), \(4\mapsto 1/8\), and so on. The construction yields a discrete distribution on \([0,1]\) with repeated values and a long tail of increasingly fine dyadic categories.

Figure 2 is obtained from a simulated population of size \(N=1000000\). For each \(n\in\{10000,50000,75000,100000,200000,250000,500000,1000000\}\), we draw confidential subsamples of size \(n\), generate synthetic data using the Dirichlet-process posterior-predictive mechanism, and compute \(\mathcal{W}_1\left(e_m^{(\mathbf{Z})},e_n^{(\mathbf{X})}\right)\). The reported values are averages over \(100\) independent runs, with \(99\%\) confidence bands.

8.3 Details on the California census dataset↩︎

In Section 4.3, we use the PINCP variable from the \(2024\) \(5\)-Year Public Use Microdata Sample from the American Community Survey. Observations with missing or non-positive income are removed. The remaining values are transformed by taking logarithms and then applying min-max scaling, so that the final data lie in \([0,1]\). The cleaned and transformed dataset contains \(11918162\) observations, \(32393\) distinct recorded values, and \(7689\) singletons.

The Dirichlet-process posterior-predictive mechanism uses \(H=\operatorname{Unif}[0,1]\), \(\theta=1\), \(\varepsilon=2\), and \(\delta=10^{-5}\). The released sample size is chosen as the largest integer satisfying the privacy bound in Theorem 2, which gives \(m=119\). The histogram mechanisms use \(300\) bins and the same released sample size. The perturbed histogram uses Gaussian noise calibrated to the \((\varepsilon,\delta)\)-differential privacy target. The smoothed histogram is composed with an \((\varepsilon,\delta)\)-differentially private Gaussian perturbation of the histogram counts. The Wasserstein boxplots in Figure [fig:wass95boxplots] are based on \(100\) independent runs of each synthetic-data mechanism.

References↩︎