On the Inherent Privacy Properties of Discrete Denoising Diffusion Models
Authors: Rongzhe Wei
Eleonora Kreacic
Haoyu Peter Wang
Haoteng Yin
Eli Chien
Vamsi K. Potluru
Pan Li
Venue: Accepted by TMLR ()

Abstract: Privacy concerns have led to a surge in the creation of synthetic datasets, with diffusion models emerging as a promising avenue. Although prior studies have performed empirical evaluations on these models, there has been a gap in providing a mathematical characterization of their privacy-preserving capabilities. To address this, we present the pioneering theoretical exploration of the privacy preservation inherent in \emph{discrete diffusion models} (DDMs) for discrete dataset generation. Focusing on per-instance differential privacy (pDP), our framework elucidates the potential privacy leakage for each data point in a given training dataset, offering insights into how the privacy loss of each point correlates with the dataset's distribution. Our bounds also show that training with $s$-sized data points leads to a surge in privacy leakage from $(\epsilon, \mathcal{O}(\frac{1}{s^2\epsilon}))$-pDP to $(\epsilon, \mathcal{O}(\frac{1}{s\epsilon}))$-pDP of the DDM during the transition from the pure noise to the synthetic clean data phase, and a faster decay in diffusion coefficients amplifies the privacy guarantee. Finally, we empirically verify our theoretical findings on both synthetic and real-world datasets.

Published in Transactions on Machine Learning Research (06/2024)
On the Inherent Privacy Properties of Discrete Denoising Diffusion Models
Rongzhe Wei
amgzhe.wei@ggeee edu
ECE, Georgia Institute of Technology
Elconora Kreačíć
J.P. Morgan AI Research
Haoyu Wang ECE, Georgia Institute of Technology
Ghogu.wang@ggteen
Haoteng Yin
ginht@yurdue..m edu
CS, Purude University
Eli Chien ECE, Geongia Institute of Technology
ichten6@gatech.com edu
Vamsi K. Potluru
womsik.pottrrreipnccasse
J.P. Morgan AI Research
Pan Li
ponli edu
ECE, Georgia Institute of Technology
Reviewed OpenReview: https://openreviien net/ forum? id= UnU6CBCUOF
Abstract
Privacy concerns have led to a surge in the creation of synthetic datasets, with diffusion models emerging as a promising avenue. Although prior studies have performed empirical evaluations on these models, there has been a gap in providing a mathematical characteri- nation of their privacy-preserving theoretical exploration of the privacy preservation inherent in discrete diffusion models (DDMs) for discrete dataset generation. Focusing per-instance differential privacy (pDP), framework elucidates the potential privacy leakage for each data point in given training dataset, offering insights into how the privacy loss of cach point correlates with the dataset's distribution. Our bounds also show that training with s-sized data points leads to a surge in privacy leakage from (e, O (zzz)) )DD to (c, ((2))) from the pure noise to the synthetic clean data phase, and a faster decay in diffusion coeffi- cients amplifics the privacy guarantoc. Finally, we empirically verify our theoretical findings on both synthetic and real-world datasets.
capabilities. To address this, we present the pioneering
of the DDM during the transition
1 Introduction
Discrete tabular graph datasets with categorical attributes prevalent in many privacy-sensitive
domains [Vatsalan et al. 2013 Pourhabibi et al. 2020 Li ct al., 2021 Shwartz-Ziv & Armon
2022 Borisov
et al. 2022), including finance CClements et. al. 2020: Wang el al., 2021 Potluru el al. 2024 e-corneerce
Ahmmd et al. 2017 Zhang et al. 2019), and medicine (Duvenaud et al. 2013 Schork 2015 Ulmer et al. 2020
For instance, medical rescarchers often collect patient data, such as racc, gender, and medical conditions,
in discrete tabular form. However, using and sharing data these domains carry the risk of revealing personal information (Abay et al. 2019). Studies have shown that is possible to re-identify individuals

---

Published in Transactions on Machine Learning Research (06/2024)
Diffusion Process
Training Datuset
Transition Kernel
Trunsition Kernel
11
and) 11
v(
Q: azI (1 - an)
<(v.) Qui = ang + (1
k
Prior Distribution
dimensions
<(vr)
Generated Dataset samppee
0
Noise-free Regime
Generation Process
Noisy Regime
www.............................
Signiffcant Privacy Leakage de
Miner Privacy Leakage C2
Figure 1: An Illustration of Discrete Diffusion Models (DDMs).
in supposedly de-identified healthcare data (MeGuire & Gibbs
2006 El Emam et al. 2011 1. To address
these types of concerns, publishing synthetic datasets with privacy guarantees has been proposed as a way protect sensitive information and to reduce the risk of privacy leakage (Choi et al.
2017 Patel et al. 2018
Tucker et al. 2020 DuMont Schütte et al. 2021).
Previous research has explored discrete synthetic database releasing methods (Zhou et al. 2009b B Ju
et al. 2013 Li et al.
2023).
Many of these methods employ data anonymization techniques (Sweeney 2002
Li et al. 2006 Liu & Terzi
2008
Lu et al., 2012) or focus on private statistics/statiittiin
models (aaa
ct al. 2011 Jorgensen et al.
2016
Balog al. 2018 Harder ct al. 2021). In the former category, k-
anonymization (Sweeney] 2002)
directly works on anonymizing categorical features but it be vulnerable to
the attackers with background knowledge [Machanavajjhala et al. 2007 Alternatively, methods using private
statistics models concentrate on sharing specific private statistics (Harder et al. 2021 or privatizing model
parameters Hardt et al.) 2012 Zhang et al. 2017). However, these techniques can sometimes misrepresent the original distribution or reduce sample quality by adding noise directly to model parameters.
Neural network (NN)-based generative models have been leveraged various domains on account of their ability in learning underlying distributions (Austin et al., (021)) Recently, discrete diffusion models
(DDMs) (Hoogeboom et al. 2021 Austin et al. 2021 Campbell et al. 2022 Gu et al. 2022. Vignac et al. 2022). typical reprosentative of diffusion models (DMs), have emerged as powerful class of generative models for discrete data and demonstrate great potent ial to generale samples with striking performance (Haefeli et al., 2022; Zheng et al. 2023). DDMs are latent variable generative models that employ both a forward and reverse Markov process (See Fig. D. In the forward diffusion process, each discrete sample is gradually corrupted with dimension-wise independent noise. This is often implemented through the use of progressive transition kernels, which yields not only high fidelity-diversity trade-offs but also robust training objectives (Dhariwal & Nichol 2021). On the other hand, the reverse process learns denoising neural networks that aim to predict the noise and reconstruct the original sample. Despite the impressive performance of DDMs, it is still unclear whether DDMs trained on sensitive datasets can be safely used to generate synthetic samples.
Efforts have empirically examined the privacy implications of DMs. While previous literature suggests that DMs generate synthetic training data to address privacy concerns (Jahanian et al.) 2021 Carr 2022). recent studies have shown that DMs may not. be suitable for releasing private synthetic data. Specifically, [u] ct al. 3 Hu Pang (2023) conduct membership inference attacks on DMs for text-to-image tasks and demonstrate that membership inference poses a severe threat in diffusion-based generation. Besides, studies show that DMs memorize training samples (Somepalli et all 2022 Carlini et al.] 2023). Although there exist practical observations for privacy properties of DMs, there is limited rescarch aimed at mathematically characterizing the privacy guarantees of data generated by DMs. Moreover, understanding privacy guarantees may guide practitioners to determine whether additional mechanisms, such as DP-SGD (Abadi et al. 2016), PATE Papeenot et al. 2016), should be incorporated to meet practical privacy requirements.
Differential privacy (DP) (Dwork et al. 2006 2014). the most commonly used algoritham-centric framework to characterize the privacy guarantee of an amg, is derived from the worst-case dataset. However, in the
2

---

Published in Transactions on Machine Learning Research (06/2024)
context of synthetic data sharing, the characterization of privacy leakage is about the syuthetic dataset (the algorithm output) rather than the generative model (the algorithm itself), and the learned data distribution to generate synthetic data strongly depends on the empirical distribution of the data points used for training. Therefore, a privacy guarantee that may incorporate the distributional characteristics of data points in the given training dataset may offer a far more accurate privacy characlerization than the worst-case analysis. Such data-dependent analysis may help practitioners learn which data points in the training dataset tend to introduce privacy leakage concerns in the generation process and thus design the relevant protection strategy.
In this paper, we take the first step to analyze the privacy guarantees of DDMs for fixed training dataset. Specifically, we leverage the data-dependent privacy framework termed per-instance differential privacy (pDP), which is defined upon an instance in a fixed training dataset as outlined by (Wang, 2019). The analysis of pDP allows for a fine-grained characterization of the potential privacy leakage of each data point in the training set. This offers data curators a better understanding of the sensitivity of training data.
Our analysis considers a DDM trained on samples and generates m samples, and we keep track of the privacy leakage in each generation step. We prove that as the data generation step transits from t = T (noisy regime) to & 0 (noise-free regime), the privacy leakage increases from (e, O ()>= to (c, O )-PD where the data-dependent term is hidden in the big-O notation. Consequently, the final few generation steps (ag + 1 in Fig. I dominate the main privacy leakage in DDMs, Further, our analysis demonstrates that the privacy bound (11/s) is light when m = 1, emphasizing the inherent weak privacy guarantee of DDMs. Moreover, faster decay in diffusion coefficients yields better privacy preservation. Both synthetic and real dataset evaluations validate our thcoretical findings.
For the data-dependent part, we develop a practical algorithm to estimate the privacy leakage of each data point in real-world datasets according to our pDP bounds. We evaluate the data-dependent part by removing the most sensitive data points (according to our data-dependent privacy parameters) from the dataset to train DDM, and then evaluating the ML models trained based on the synthetic dataset generated by the DDM. Interestingly, we observe that the ML. models obtained after a part of data removal can even outperform others without such data removal. We attribute this to the fact that the removed data points are likely outliers which may be actually not good for ML models to learn from. This illustrates another potentially valuable usage of our data-dependent analysis.
To avoid any confusion, provide several important explanations for considering pDP in our work. pDP, tailored to the training set, offers data curators a more accurate and fine-grained estimation of the potential privacy leakage of each data point, compared to DP which studies the worst case and keeps agnostic to the dataset (Wang) 2019 J. However, it is crucial to understand that pDP is not a replacement for DP. Direct application of data-dependent sensitivity for noise addition is not permissible for ensuring privacy, as the added noise may leak private information due to its data dependency. Data-dependent methods such as smooth sensitivity (Nissim et al.] 2007) and propese-tast-release (Dwork & Lei 2009) may be employed, while they are beyond the scope of this paper. Our analysis is to provide insights into the inherent privacy afforded by DDMs, and to guide data curators in assessing the privacy risks associated with different parts of the dataset. We are not to develop an algorithm to match a certain privacy budget as the goal. Given this purpose, pDP is a more suitable metric than DP. In practice, the pDP assessment is expected to be kept confidential and used by the data curators to understand the dataset and evaluate the potential privacy leakage if one uses DDMs generate synthetic datasets.
1.1 More Related Work
A significant amount of research has been conducted on the subject of publishing privacy sensitive data (Ji et al. 2014 Baraheem & Yao 2022). As of now, traditional non-deep learning techniques for preserving privacy while generating discrete data can be broadly classified into two categorics: (a) Data anonymization-based approaches. These methods employ a variety of techniques to directly sanitize data to prevent easy re- identification (Abay et all, 2019). One most popular framework is termed k-anonymity (Sweeney 2002) that requires each record is indistinguishable from least 1 other records with respoct to certain identifying
attributes. Several extensions of this framework have been proposed in (LeFevre et al. 2005
Aggarwal
et al. 2005 Machanavajhhala et al. 2007 Li et al. 2006 Truta & Vinay 2006 Machanava hala al. 2008
3

---

Published in Transactions on Machine Learning Research (06/2024)
Liu & Terzi
2008 Liang & Samavi 2020 However, these methods are typically prone to various privacy
attacks (Machanavaijhalla et al. 2007]. (b) Methods based on statistical models or private statisties.
Barak et al. (2007) employed Fourier decomposition and prior knowledge to release low-dimensional data
projections. Zhou et al. (2009b) proposed a database compression procedure based on low-rank random affine
transformations and publish low-dimensional data. Other works along this line include (Liu el al. 2005
Zhou
ct al. 2009a Ding ct al., 2011 Cormode ct al., 2011 Kenthapadi et al. 2012 Cormode et al. 2012) Note
that these works can work for both discrete and continuous data. Furthermore, Balog et al. (2018) introduced framework employing kernel mean embeddings (Smola et al., 2007) in Reproducing Kernel Hilbert Space, and ensuring privacy by using synthetic data approximations to enable safe data release. Nevertheless, these methods usually suffer from poorly generated sample qualities. With regard to this, establishing NN-based private models is a promising way to enhance sample qualities due to the great expressive power of deep networks.
Hitherto, there are studics on NN-based private models but few analyze the inherent privacy of the model itself. In (Lin et al.) 2021), it was shown that vanilla. GAN trained on samples inherently satisfies a weak (e, O (O))))))) )-D guarantee when releasing samples. In this work, our results demonstrate that DDMs provide weak privacy guarantecs in the same order as GANs. But note that Lin et al. (2021) did not provide a Bata-dependent bound. Their bounds are in the order form and cannot be explicitly computed from data curator's s side for a given training dataset. Because of such weak inherent privacy there were efforts to bring additional privacy techniques into the model, such as DP-SGD (Abadi et al., 2016). Xie et al. (2018) proposed DPGAN that integrates modified DP-SGD in WGAN to ensure privacy for GAN-generated samples. Dockhorn et al. (2022) applied DP-SGD to privatize model parameters in continuous DMs for image data without analyzing the inherent privacy of DMs. Recently, Ghalcbikesabi et al. (2023) have showed that
fine-tuning pre-trained diffusion model with DP-SGD can generate verifiable privale synthetic data for the dataset used for fine-tuning.
2 Preliminaries
We start by introducing notations and concepts for analysis. Let [n] = {1, ...,,,..n]] n and X" represent an n-dimensional discrete space with each dimension having l categorics, i.c. x = X1 x ... x X, with X; = [k],, E [m]. We assume that training datasets V reside X"", implying samples are vector-valued data of n entries, each from one of the categories. Although we assume consistent categories across columns, our analysis can account for datasets with varied category counts using the maximum category count.
Per-instance Differential Privacy. DP (Dwork et al. 2006 2014 is de-facto standard to quantify privacy leakage. We adapt DP definition for specific adjacent datasets, introducing per-instance DP:
Definition 1 ((c, Pe--eernne Differential Privacy (pDP) (Wang 2019)). Let Vo be a training dataset, v E Vo be fixed point and M be a randomized mechanism. Define adjacent dataset VI = VoM(') We say M satisfies (e, dDP with respect to (Vo, v*) if for all measurable set O C (M)) {i.j} = 10,
P(M(1) E EO) S P(MM))) E
(1)
It is important to highlight that pDP is uniquely defined for a specific dataset-data point pair. This capability is crucial for understanding the privacy leakage of the given dataset, as elaborated in Sec. 4 Additionally, by taking the supremum over all conceivable datasets Vo and points v", we can obtain DP from pDP when considering model releasing scenario (Theorem E. A more comprehensive discussion of the DP guarantees associated with DDMs is provided in Appendix.
Discrete Diffusion Models. DDMs (Hoogeboor el al. 2021 Austin el al. 2021 Vignac el al. 2022 Haefeli et al.) (022) are diffusion models that can generate categorical data. Let V, denote the data random variable at time The forward process involves gradually corrupting data with the noising Markov chain g, according to q(vi.T|vo) = I ((v./v=-1), where V1.7 = VI, V2,..., VT On the other hand, the reverse process, (Vo.r) = p(vr) I1= (V(V, [v),, gradually reconstructs the datascts starting from a prior p(Vr). The denoising neural network (NN) learns po (v--1lv) by optimizing the ELBO, which comprises three loss terms: the reconstruction term (I,,), the prior term (I,p), and the denoising term (Tx). represented in the
4

---

Published in Transactions on Machine Learning Research (06/2024)
following equation Ho et al.
2020
T
E (vo Po Po (volvi)) DKL (oolv
B Bo(yslva) (ettvlva))PKL(A(ee (Pkula(v--llve Vv--
(2)
Reconstruction Term Lr
Prior Term Lp
Denoising Term L
Specifically, the forward process can be described by series of transition kernels (Qihermaatjn where for any entry vt, [Qij.. = g(vi hlvi-1 1) represent the probability of a jump from category 1 to h on the i-th entry at time t. Since for each entry i the number of categories is the same, we can rely on the same transition kernels for all dimensions and use Qs instcad of Q; Let Q, QiQ2..Qe denote the accumulative transition matrix from time 1 to time t. We use a uniform prior distribution p(Vr). The corresponding doubly stochastic matrices is determined by series of important parameters termed diffusion coefficients (La,, [T]]a, E 1))) which control the transition rate from original distribution to uniform measure. Specifically, define Qr = 0+ (1 - oz)
- and then Q: = ā, + (1 - ā,) 112 where ã₂ = -I at- In the reverse process, denoising networks are leveraged to predict ps po(vi-1 (v.) in hope of approximating q(v:-I vo). In practice, instead of directly predicting
(z)
denoising networks are learned predict clean data Vo time with noisy V, as input, i.e. Po (vo v.). To train the denoising network, needs to sample noisy points from g(vx/vo), and feed them into the denoising network Φi and obtain ps vv). Specifically, adopt
Lirain Div M
Ev, Bv VOEV
Σ
Σ LCE LCe( Polvlvv))))))
(3)
This loss serves as the basis for our later sufficient training Assumption In the generation process, we need to bridge the connection of po(v,-1/v; and (Volve), which in practice depends on a dimension-wise conditional independence condition (Vigacc et al. 2022
Ps Pv(Vi-Ilv)) = II Pe ( (v.) = II Σ SE[m] LEN:
g(v; /Ve, vo = -1pp(vv = 1lv.).
(4)
KE(n)
Other Notations. Given two samples v and V, let @(v, v) represent the count of differing entries, i.e., @(v, v) = # + v E [n]]. For 7 E [n] and v E V1, define N2(v) = l[vv E Vi @(v, S 7) and Dill (v Vilv' = 1) the set of data points with fixed-valued entry. We use D and ||rv for KL-divergence and total variation. Let ,4, 1+(k-1)as and 14 = 1-a; represent one-step transition probabilities to the same and different states respectively time while μ 1+(k-1)a. and 1hg I-oe are the accumulated transition probabilities. Transition probability ratios are defined as RG = = and R. = A larger ratio indicates a higher likelihood of maintaining the same feature category in the diffusion process. Moreover, define (+)+ max 0}.
I
P.
M.
3
Main Results
3.1
Inherent Privacy Guarantees of DDMs
First,, define the mechanism under analysis. Let Mc(V:m) represent the mechanism where, for an input dataset V, it outputs samples generated at time using the DDM's generation process. Specifically, M)) signifies the final generated dataset by DDM. In the paper, we focus on the behavior of M, in the generation process. Below, we outline the assumptions:
Assumption 1 (Sufficient training of Φ). Given dataset V. let vo denote the predicted random variables at time O. Let é denote denoising NNs trained on dataset V. We say Assumption | is satisfied if there exist small constants 74 > 0 such that Vv, E x
D
& nh Vi E [n], Vi E (T).
(5)
5

---

Published in Transactions on Machine Learning Research (06/2024)
Assumption 2 (Gap between Forward and Backward Diffusion Paths). Given dataset V, let V. denote the random variable sampled from intermediate distributions at time t in both the forward process (following ((ve)) and backward process (following pv(v))). We say the Assumption 2 is satisfied if there exists small positive constant 9 < 2 such that
l1a(v)) - Po(ve)llTV S 9r, Vt E [T].
(6)
Assumption | states that denoising networks, when trained using the loss function in Eq. (3, can effectively infer clean data from intermediale noisy data distributions. Given a sufficiently expressive model, we expect
Yt to be small. Assumption 2 asserts that diffusion and generation paths are close, which is a reasonable assumption due to the recent analysis (Campbell ct al. 2022). However, one cannot use Eq. (6) to derive privacy bound directly as closeness in total variation does not imply DP in general though the reverse could be true (Bassily et al. 2016).
With above assumptions, we investigate the flow of privacy leakage along generation process. Our analysis centers around the inherent privacy guarantees of DDM-generated samples at specific release step, denoted Tn- Later, will show that our privacy bound is tight when generating single sample (m = 1).
Theorem 1 (Inherent pDP Guarantees for DDMs). Given a dalaset Vo with size [Vo = s and
data point v* E Vo to be protected, denote VI such that Vi = -o'lv''. Assume the denoising networks trained on Vo and Vi satisfy Assumption | and Assumption D Given a specifie time step Tri, the mechanism Mr.(:m) satisfies (e, oPPDP with respect to (Vo,") such that given e,
T
min 4N (v')
}
n
n(1
R.
+ o VT 10(
fit + 9o 1(e(1-
8(Vo. v²) S m
(7)
5v
52
Main Prinacy Term
Ervor Term
where 1/2, nt, of are dota-dependewt quantities determined by v* and Vi- Define similarity measure Sim(yy, V) Evey Rí --=((v-'') Then, Vr,, Te, of follow
n | Söm v², Vi)
p4
Σ 1=1
log 1+ Simlv",
R2 -1
8
R
Sim(vv, V1) +
And, Be, of are the smallest ne 21, nJ, of E 10, Tt
n-m which satisfy
qfe
log 11-1ma ( )1/
11: log n(1-p/)
log ((p))
+ 2 log Rs
kpp a7
-2
Tt
log 0((1 + oz )10 +
log 12
where {(n) = (s- (V_NN(vV)))N, that represents the ratio between the numbers of points outside the n- n-ball and inside il.
Theorem D quantifies the privacy leakage of specifie point v² in training set Vo- The privacy bound comprises main privacy term that represents the inherent pDP guarantees for DDMs, highlighting the data-dependent nature of our bound, and error term stemming from denoising network training and path discrepancies. Those data-dependent quantities are complex to maintain a tight measurement for a dataset-data point pair. Next, we will further explain these quantities.
First, as the generation process forms a Markov chain where the transition probability (o(v(t-1)) is learned from training, each generation step will leak some information from the training dataset. can be shown that the majority of such leakage, represented in the pDP bound (in the appendix) follows
(10)
where let V. a represents the random variable of the generated data at time of the generation process when the diffusion model gets trained the dataset Vx, X E (0, 1} and d (v) Exeço. DRu.po(Vi-spllnn

---

Published in Transactions on Machine Learning Research (06/2024)
(l v)) with - X, which characterizes symmetric distance between two conditional distributions characterized by the learned diffusion model. Essentially, the three data-dependent quantities Vr, nh, of are to bound Eq. (10).
Quantity th: As shown in Fig. 29t quantifies max, (v) where the maximum is achieved at the removed point = v* (green Fig.
closer inspection reveals that 8h depends on the terms Sim(v", Vi) and Sim(v", >/("")) ). By the definition of w, these terms assess how v aligns with the remaining points in V1.
Evolution of t/u. During the generation phase, progresses from T to 1, the values of ب increase from (x) to (1). This implies that the potential privacy risk escalates as the data generation process evolves from noisy regime to noisc-free regime.
Similarity
R
Intermediate
Per-instance Privacy Leskage
Generated Measure pulvol
True Measure
Delta Measure
n
c/mm
Privacy Leakage
(v
Eq)(9)
Upper Bound
Figure 3: Illustration of the correlation between dataset similarity (Sim(v., Vo Vo).v.)), Vv, E Vo) and pDP Leak- age.
Figure 2: Illustration Data-dependent Quantities.
Quantities Te and c: It is evident that the intermediate generated mcasure Po(V:jo) (blue in Fig, 2 diverges from the delta measure on the most sensitive point. &v=v" (green). Therefore, the actual privacy leakage characterized by (v) (yellow) averaged over the measure (V is much less than its maximum. To provide a tight characterization of such, the two quantities 1)t and of are introduced to define a local region S (v' E X" : ((v, v') S (1 (1+00 m))m)} centered on vulnerable point v", within which the privacy leakage can be bounded by the sum of (a) Po 8) maxves d(t) (v) with small Po(V. E E) and (b) Po(Vip & +) maxyes (v) with a small maxves (v). (m,, c) shown in Eq. gg are chosen to properly balance these two parts. f/t and of always exist: Note that when 7/+ = n or of = n/Tt 1, the right-hand side of either inequality in Equation (9) approaches -oo (log 0). In fact, both of the RHS's of the two inequalities decrease w.r.t. Ne and et. So, in practice, the smallest TJ, and of can be found via binary search given the dataset Vo and v*.
Evolution of (1 + c.),.. For each time step t, the smallest value of (1 + ci) m is chosen as the radius. As progresses from T to 1, the value of (1 + ct m monotonically decreases. When ā₂ approaches 1 for smaller values, (1 +1+0 ot yn, tends to zero, i.e., S only includes v*. The reason that, as smaller values, different data points are less mixed with others (bocause of less noise addod in the forward process), the privacy Icakage of V becomes more concentrated around the changes of the likelihoods of the generated data points that look like v*, thus calling for decrease of the radius. To consider the impact on the bound in Eq. (7). the number of data points in this region N(1+c7m (v*) will decrease from to 1 as t changes from T to 1.
Discussion on Theorem I. Based on the previous discussion, as L decreases from T to 1, Nate (/*)/s changes from O.(1) to O,(1/s) and 1/ changes from (.(2)) to O,(1). Consequently, the privacy leakage for each-step DDM-generated samples gradually increases from O, (#) ))(((1 - e to (,( - e))
This implies a natural
tradeoff for the data generated by DDMs. In practice, to guarantee the data quality, we often release the data in the noiso-free side (t= 0), where only a weak privacy guarantee of approximately (c, (m(mmmmmmmmee e")) can be achieved. To enhance data privacy, we may expect release the data generated with larger step 1 1.
7

---

Published in Transactions on Machine Learning Research (06/2024)
Data-dependent Quantity 2
Dala-dependent Quantity (1 +
Privacy Leakage in Generation Process
Fallure Probabiltty (6)
10 10'1
10-
10"
1050
0.5
5.0
7.5
16,0
125
15.0
175
0.0
2.5
5.0
7.5
16:0
12.5
15.0
17.5
0.0
2.5
5.0
7.5
10.0
12.5
15.0
17.5
Each Ditfuston Step (t)
Each Diffusion Step (t)
Each Diffusion Step (t)
Figure 4: pDP Leakage in Eq. 7
LEFT: Characterization of .o. MIDDLE: Characterization of (1 + oī me-
RIGHT: Characterization of Privacy Leakage (Main Privacy Term). Experimental Setup: Given specific DDM design k 5, n 5,T 20, 10 trained on dataset with 1000 following the distribution in See. 3.3 with
parameter p. Fix v' where each column has mon-majority category. Results are based on 5 times independent tests.
This result also reveals that the inherent privacy guarantecs of releasing data generated by DDMs is weak (xx ((m/s)), in the same order of guarantees for GAN-generated samples (Tin et al. 2021 This characterization also matches many recent empirical studies that have shown concerns on privacy leakage due to publishing data generated by DMs (Hu & Pang 2023 Carlini et. al., 2023: Dockhorn et al.] 2022
While privacy budgets for all data points maintain the same order in relation to the sample size, the contacts can differ markedly across data points. Intuitively, data point v E Vo with less similarity with the other data points tends to have higher privacy leakage. This is indicated by Eq. 8 where a smaller similarity
EverA R -(v",v) leads to a larger pDP leakage (as illustrated in Fig. 3
The upper bound for t = 1 with a dependence on the dataset size (x(2) demonstrates a weak privacy guarantec given by DDMs, as this is on par with the privacy implication of the Strawman approach that uniformly al random samples from the original dataset and publishes the samples. However, we emphasize that this is not due to a loose analysis, as the following will provide a lower bound of such privacy leakage due DDM generation in the same order. Beyond this, our upper bound is valuable as it elucidates that releasing dataset at an earlier stage (with a larger step) generated by DDMs could potentially strengthen the privacy guarantee to (2)) Moreover, our upper bound specifies the influence of diffusion coefficients and dataset distributions on the privacy bounds, which the Strawman approach by publishing the samples from the original dataset cannot tell. More details will be discussed in Sec. 3.2
Tightness of Privacy Bound w.r.t Sample Size. In Theorem I the privacy parameter of å scales as !2(.) with sample size. Here we establish a lower bound for with respect to the sample size by evaluating the worst-case scenario and show that (11/s) is the optimal bound that DDM can achieve inherently for m = 1. For illustrative purposes, consider the case where n = 2 with two distinct categories. Define adjacent datasets: Vo= 110,0' ".., [0. 0l" [1, [1, (]T) and V1 = Vol 177)
Theorem 2 (Lower Bound on Inherent pDP Guarantees for DDMs). Assume the denois- ing networks are perfectly trained. Given a diffusion model architecture design (Sigmoid Schedule at Sigmoid(3) Sigmoid((1) (ammoit())-Ssmmoidt Sigmoid(3)-u.3 T 10), there exist an adjacent dataset Vo, V1 = VoY(v"} with feature dimension n = 2 such that the mechanism Mol:;) 1) does not satisfies (0.04,8)-pD0) with respect to (Vo, v*) for any ue
Regarding lower bounds on (c, 8)-DD under general model configurations, including diffusion schedules and diffusion steps, please refer to Appendix D
Discussion on the Inherent DP Guarantees for DDMs. As mentioned in Sec. 2 DP guarantees can be obtained from taking all conceivable datasets Vo and points v*. Therefore, by considering the worst case adjacent dataset pair, we derive the DP privacy bound for DDMs:
Theorem 3 (Inherent DP Guarantee for DDMs (Informal)). Given any adjacent datasets Vo. V1. Assume the denoising networks trained on Vo and Dn satisfy Assumplion 7 and Assumplion Given specific
8

---

Published in Transactions on Machine Learning Research (06/2024)
time step Tet the mechanism (r.(;m) satisfies (c, 8) difffeerfee privacy such that
5 S m
min 4N
n
1eth
+0
+ VT tt ) ( -
(11)
ghz
8
Main Privacy Term
Feror Term
where ve, C7 fe. St are quantities that only depend on the diffusion coefficients, and č₁ t meet certain radius selection crileria (refer Eq. (50) and Eg. (49) in Appendia Fy. As progresses from T 1, the value of 89t increases from O₂ (+) Os(1), while No.l monotonically decreoses from O.(1) to O2 (1)
As indicated by Theorem 3 akin to findings from pDP, during the generation process, privacy leakage intensifies from O₂ m2
([e(1-eTT))) - -]] to O₂ m /[e(1 - e)) The formal presentation and analysis of DP
guarantces for DDMs are detailed in Appendix
3.2 Impact of DDM Coefficients and Dataset Distributions on the Privacy Bound
Influence of Diffusion Coefficients. The privacy term is largely influenced by the proximity between v* and V4. As time progresses, this similarity is governed by the transition ratio Rg A faster rate of diffusion coefficients going to zero boosts this ratio, enhancing the privacy guarantoe. Experiments in Sec. 4 validato this observation.
Impact of Dataset Distribution. We find that th, has major effect on the privacy bound. t/ is influenced by the similarity between the additional point v* and [o) If v* is far away from (close to) the rest points in Vo, then (am t) becomes small (large) and the corresponding term s s become large (small), which indicates weaker (stronger) protection v*. This indicates that points with notably low Sim(Vo') {v*) J, t), are probably sensilive points in the dataset.
3.3 Characterizing Data-dependee Quantities under Simple Distributions
Here, we consider the training dataset sampled from some specific distributions to further illustrate the data-dependent quantitics.
Consider a distribution such that each column independently takes value 1 [k] with probability p (p 2 })) and any other k - categories with probability 1... Let v* take non-majority category ((v*)* #1) along all n columns (termed non- non-majority points, which thus tends to have higher privacy leakage) and the rest points in Vo (v*) are sampled from the distribution. We have the following characterization (For detailed explanations and proofs, please refer to Appendix F7
.. For sufficiently large s (detailed in appendix), with high probability, 608-2
where Te := 1 (1 1.3). In the noisy regime (a large t, Pr + 1), T 1, ahe Oz ( For
distribution characterized by larger skewness, i.e., larger we have smaller result in larger 39r Fig. (LEFFT) precisely matches the above conclusions.
1.
Th, ct. For a sufficiently large (detailed in appendix), sufficient condition for and of to satisfy Eq.
is
n log(s (8
P 0t-1 log
1-1 log ZE n- log I-p
Kyp 17
T 2 n 2log
c
(12)
k-1 /-p/ logamax| np.
13)
k-1 + log log I-p
est
In the noise free regime (a, + 1), n + 0, while the noise full regime (ar - 0), Tt + n. From noise free regime to noisy regime, F increases, et + R-me Furthermore, as we risc the skewness (p) of the distribution, the R.H.S of Eq. 12 monotonically increases, and results in larger values for th and c. Fig (MIDDLE) matches the above conclusions.

---

Published in Transactions on Machine Learning Research (06/2024)
3.4 The Algorithm for Evaluating Privacy Bound in Eq.
given Dataset
In practical situations, when data curators release synthetic data, it is crucial to assess the privacy safeguards of the mechanism trained on a specific dataset. This ensures the synthetic data upholds privacy and the confidentiality of the training data's sensitive information. To this end, we introduce Algorithm [ (paired with Algorithm 2), to compute the privacy bound, enabling direct per-instance privacy leakage calculation for DDM-generater datasets given particular training sets. Specifically, for each v", we determine th,, 1)t and of compute 5(v", Vo) using Eq. (7). Using this algorithm, data curator can have better assessment of the potential privacy leakage of each point in training set and may exclude sensitive points v (outliers) with high 5(v", Vo) to enhance privacy protection. This approach's 's efficacy is confirmed with real dataset. experiments in Sec. 4 The total time complexity of the algorithm is further analyzed in Appendix C
A Algorithm Privacy Bound for Discrete Diflusion Models
1: Input: Datasct Vo; Diffusion Step: T; Diffusion Coefficients: (au (auhET(T
2: For each v, v' E Vo, calculate and store (vv,v" in Ti and (v) in To for n E [n].
3: Use diffusion coefficients harherr to calculate {ur Me M4 Pt (1.........TT Define empty array Privacy_Bound Bound [].
for For every V E Vo do Define empty array Arraye; 0-
for 4 1 to T do
8:
for t 1 to n do Calculate of using Alg.; (Algorithm 2 and determine {1/s²t with Ti and {Hr Mi }. If m meets the condition in Eq. 99) using N,, (v) and Na++)) (v) from T2, then break. end for Array,; [t] - (1+
9:
10:
11:
12:
13: end for
14: Use Array.; to compute and append
4N 4Na1+ctm (v)
n(1
Privacy Bound - m
min
,
n
B
[E( 9
8
8th
2²
1,3
15: end for
16: Output: Privacy Bound
Algorithm Alg.r: Finding cj
1: Input: ne. Nt,
for 1= T do
if m(2%)) (2e77) n then
@ Select the smallest of E (0, n n
n-1)
such that o
1.
log 0(11+
) + 1logg
log
else if 1 S (2ep,) y then
@ Select the smallest of {1, n++1 n.42
n- 71 m
such that of 2
32
log ((1+ 1mc)
log
7: end if end for
Output: of
4 Experiments
We validate theoretical findings via computational simulations synthetic and real-world datasets.
10

---

Published in Transactions on Machine Learning Research (06/2024)
4.1 Synthetic Experiments
We first study the asymplotic behavior of privacy leakage with respect to the training dataset size 8. Given a DDM with 100 diffusion steps and trained with linear schedule a = =1 - 4. we fix v and increase the number of samples in the training set from le4 to 1c7, ensuring that the newly added samples satisfy @(v, v*) = n, which makes v* with high privacy leakage risk. Results shown in Fig. (LEFT, MIDDLE) confirm our theoretical prediction that, in noise-free regime (t 1, Fig- 5 (LFFT)), the main privacy term in Theorem
I is (2),), which is almost a linear decay with a slope of in the logarithmic scale (all lines in the figure). On the other hand, in the noisy-regime (t = 50, Fig. P (MIDDLE)) the privacy leakage term decays faster at. the rate of (z))), which is evident from the linear decay with a slope around -2. In the second experiment, we examine how decay rate of diffusion coefficients affects the privacy bound. Given specific v* (non-majority categories along all entries), we sample the training set from the distribution with p p= 0.5 in Sec. 3.3 We consider two noise schedules: linear schedule and sigmoid schedule, In Fig. 3 RIGHT, the red line denotes the linear schedule with decay rate E (0.1,0.3, 0.5, 0.7, 0.9} and the blue line denotes the Sigmoid schedule where decay rate increases from 2.5 to 5. ô decreases along both two lines as we increase the decay rale of diffusion coefficients. This indicates that faster decay rate in diffusion coefficients implies better privacy.
More results discussing privacy leakage and the behaviors of data-dependent quantities under various DDM configurations are given in Appendix|
First Step Privacy Lege wnt Sample Size
Middle Stop Privacy Leackage win Sample Size
The Privacy Bound Noise Schodules
Paluue Probabiicy (8)
Pallura Probability 003
10-0 16-- 1r-17 10-1
Musil hhoke 2e tre Liwer
Diroayy Zedput an Liner
Decay Hate ())
Decoy Rotoo (clope)
15-3 10
Iiie Baggere)] sungle Sou 30083
30 25
1-1
10
Number Samples (8)
Number of Samples (8)
Fatlure Probobility (6)
Figure 5: LEFT: Privacy Leakage at t= 1 (Noise-free Regime). MIDDLE: Privacy Leakage at = 50 (Noisy Regime). Right: Privacy Leakage w.r.t Decay Rate under Linear (a. decay rate 4) and Sigmoid (o, = Sigmoid (8+ decay rato) 3 edecay rate), Schedules. Results are based 5 times independent tests.
Sigmoid(3-decxy 10,5
4.2 Experiments on Real Datasets
4.2.1
Effectiveness of Privacy Bound Algorithm for Data Sensitivity Assessment
In this series of experiments, we aim to showcase our privacy algorithm's effectiveness in assessing the scnsitivity of individual data points within real-world datascts and to delincate the relationship between sample privacy leakage and dataset similarity (as illustrated in Fig. 3) Additionally, from data curator's perspective, we explore the potential of our algorithm assisting in outlier removal, which may enhance privacy protections while maintaining utility performance. It is important to note that the use of pDP assessment itself is kept confidential to the data curator, safeguarding against any privacy concerns. We evaluate our algorithm on three benchmark datasets: Adult (Kohavi et al., 1996), German Credit (Hofmann) 1994), and Loan [ItSSuru) with (# training samples, # feature dimensions, # categorics) of (30718, 9, 5), (1000, 10, 5), and (480, 11, 4) (see Appendix H for details).
Experimental Settings. Our study, approaching from the perspective of data curator who preprocesses the datasct, investigates how varying the sensitive data removal ratio according to our per-instance privacy bound assessment can potentially assist data curators in eliminating outliers to enhance privacy protection.
Specifically, we calculate the privacy budget for every point in the dataset according to Eq. (7) via Algorithm [ and remove the most sensitive points according to the assessment the datasct amounting to a specific portion which is controlled by the removal ratio. The removal ratio ranges from 0.01 to 0.5 for the Adult and German Credit datasets, and between 0.001 and 0.05 for the Loan dataset. It is important to underscore
11

---

Published in Transactions on Machine Learning Research (06/2024)
Privacy-Accuracy Accuracy Trade otts w.r Data Removal Batio
Privacy
Accurayy orade-ofts wer Data Removal Ratio
Privacy-Acurnae Trade wext Data Removal Ratio
Conk-dben Amary
Pallure Probabikng (6)
Classl Feoaiiin Anmonery
liee 1pm 1ie
Caloso Fro trom Artou
Paflur Probabiiity
Fallurs Peraaai
Chass frantton
6.4
Mest Slactac hay
Data Removal Ratio
Data Removal Ratio
Data Removal Ratio
Privacy Siiilarity Distribution
Prisacy Siiilarity Distribution
Privacy Similarity Distribution
105
Faluro Probobbiitty (F)
12:4
Fullure Probobillty (05
Fallure Probabiiity
12-3
10-
10-1
20"1
12n1
03-4
10-3
The Seee
Tax
Taa
Taa
(105
13 200
"K5""""""
10-1
Averaged (2)
Averaged (22)
Averaged (22)
Figure 6: First Row: Privacy-utility trade-offs with respect data removal ratio. LEFT: Adult, MIDDLE: German Credit, RIGHT: Loan. Experimental Setup: DDM design: T = 10, Linear Schedule. Second Row: Visualizing privacy budget relation average feature overlap. LEFT: Adult, MIDDLE: German Credit, RIGHT: Loan.
that, after each data removal, we conduct privacy recalculation and report the mean privacy leakage (blue line) and the most sensitive point privacy budget (yellow linc) after cach data removal process in Fig. 0 (First Row). We measure utility performance with respect to downstream classification task by training a binary classifier on DDM-generated samples and evaluate its performance (red line) on the original dataset. We further illustrate the sensitive points those removed from the dataset by graphing their potential privacy leakage alongside the average overlap with the entire dataset across all feature dimensions, denoted by w. The visualizations are presented Figure (Second Row).
Remove privacy sensitive points with comparable utility. As depicted in Fig. 6 (First Row), eliminating minor proportion of the most sensitive points from the dataset results in decrease in privacy leakage. Meanwhile, the classification accuracy (red line) only gets slightly decreased: 81% - 78% for Adult, 73% + 70% for German Credit, 81.1% + 79.8% for Loan (note that for Loan we remove at most 5% data points as its size is too small) More interestingly, by removing a certain nunber of those most sensitive data points, the classification model trained over the pruned generated dataset may even achieve better performance over the original dataset, say removing 3% in Adult and 1% in German Credit. We attribute such gains to the fact that the most sensitive data points are often outliers in the dataset, which may be actually not good for training an ML model. In data visualization (Fig. 6 Second Row), we note that the data points prone to greater privacy leakage tend to have less feature overlap, indicating that these data points have a lower similarity to others in the datasct. As pointed out in (Carlini et al. 2022 the mere exclusion of the most sensitive data points from the dataset does not necessarily guarantee a reduction in privacy risks as certain inliers may become outliers post-removal, a phenomenon termed "Onion Effect". However, in our experiments, we did not observe the "Onion Effect" within the Adult dataset. Empirically, we did find that as the data removal ratios increase to a certain extent, privacy leakage ceases to decrease and may fluctuate. This can be attributed to the fact that an individual data point's privacy risk is determined by its similarity to the current dataset distribution. Simply removing certain data points does not necessarily enhance this similarity, and thus privacy Icakage may not decrease. Furthermore, decrease in dataset size also intensifies privacy leakage, Therefore, in practice, data curators should perform pDP recalculations on modified datasets with varying data removal ratios to potentially achieve better privacy-utility tradc-offs.
4.2.2 Evaluation of DDM Vulnerability to Black-box Membership Inference Attacks
In this subsection, we further investigate the privacy leakage of DDMs from membership inference attacks perspective.
12

---

Published in Transactions on Machine Learning Research (06/2024)
Black-box Attacks with No Auxiliary Knowledge: In alignment with the experimental settings delineated by (Hayes et al. 2017), this study considers black-bor allacks where the attacker has no prior knowledge or external information regarding the target model, i.e. DDM in our case, including model parameters / heyper-parameten hypothesized that the altacker possesses access to the whole datasel, denoted as X = X X non-train- Additionally, it is presumed that the adversary is aware of the size of the training set. The attack primarily utilizes the target model's generated samples to identify and exploit its vulnerabilities.
model architecture, training data, or prediction scores. For ovaluation, it is
Experimental Settings: Our experiments utilize the Adult dataset. We partition this dataset by randomly selecting 20% of the records as the training set, denoted as Xtrain, while the remainder is labeled as X non-train- We train a DDM to learn the conditional distribution of Xtrain given their corresponding labels Yerain- Next, the adversary employs a discriminative model denoted as f(: feature space X' + label space y/ (dctailed in Appendix. H which trained using two-class samples (Xgen, Ygen) generated by the DDM and denote trained model weights as Ogen- This trained discriminative model
Membership Infereace Attack on Adult
6:00 0.25 0.24 0:22 0.38
Attack Accuracy
f(: (g:0) is then used to make predictions across the entire dataset Xtrain UX We identify [erain| samples with the highest confidence values those whose prediction scores are closest to the true labels- and designate these as training members Xtrain- The evaluation of the DDMs is centered around varying the decay rate of diffusion coefficients, influencing the degree of privacy leakage in the models. The outcomes of these eval- nations, particularly the attack accuracy ( [Xtraunf(Xiai ), are illustrated in |Xaiiial
02
04
0.5 0.8
1.0
Decay Rate (Slope)
Figure 7: Black-box Attack with no auxiliary knowledge over DDMs under various designs. Results are averaged over 3 independent tests.
Fig. 7 More specifically, we examine DDMs with total diffusion steps T set to either 20 or 30, and a linear schedule defined as a - decay rate x 4. Additionally, the decay rate is varied within the range {0.1, 0.3, 0.5, 0.8, 1.0} to adjust the privacy guarantees of the DDMs, with a faster decay rate typically providing better privacy protection.
Increased Privacy Leakage Enhances Vulnerability of Models to Attacks: As illustrated in Fig. the blue and red lines represent DDMs with total diffusion steps of 30 and 20, respectively. A noteworthy observation is that the DDM with T = 30 exhibits higher attack accuracy, suggesting stronger capability for memorising training data in models with a greater number of diffusion steps. Furthermore, an increase in the decay rate leads to improved privacy guarantees for the DDMs. This enhancement in privacy is evidenced by a decrease in attack accuracy for both models (as represented by the blue and red lines), which diminishes from 28% / 29% to approximately 22%. It is important to note that the performance of both lines surpasses that of random guessing (indicated by the purple line), signifying that our target models retain training data memorization across all evaluated settings.
5 Conclusion
In this work, we analyzed data-dependent privacy bound for the synthetic datasets generated by DDMs, which revealed a weak privacy guarantee of DDMs. Thus, to meet practical needs, other privacy-preservin techniques such as DP-SGD (Abadi et al. 2016) and PATE (Papernot et al. 2016) may have to be corporated. Our findings well align with empirical observations over synthetic and real datasets.
6 Limitations and Future Work
Our research currently targets discrete-time diflusion models for discrete data. An intriguing extension of this work could explore continuous diffusion models applied to continuous data domains, such as images, which present numerous practical applications. We believe the core logic of our proof concept adaptable to continuous diffusion models, albeit some of our current arguments, grounded in the characteristics of discrete distributions, may not directly apply or might necessitate further examination.
13

---

Published in Transactions on Machine Learning Research (06/2024)
Our findings are predicated the assumptions concerning the denoising networks' expressive power and the total variation gap between forward and backward diffusion trajectories. Relaxing these assumptions can be an interesting direction for future work.
7 Acknowledgement
We extend our sincere gratitude to Zinan Lin for his insightful discussions and contributions to this project. We also appreciate the reviewers for their valuable foedback and actionable suggestions. Wei, H. Wang, H. Yi,, E. E.Chie and P.Li are partially supported by 2023 JPMorgan Faculty Award and NSF IIS-2239565.
8
Disclaimer
This paper was prepared for informational purposes by the Artificial Intelligence Research group of JPMorgan Chase & Co. and its affiliates ("JP Morgan"), and is not a product of the Research Department of JP Morgan. JP Morgan makes no representation and warranty whatsoever and disclaims all liability, for the completeness, accuracy or reliability of the information contained herein. This document is not intended as investment research or investment advice, a recommendation, offer or solicitation for the purchase or sale of any security, financial instrument, financial product service, merits of participating in any transaction, and shall not constitule solicitation under any jurisdiction to any person, if such solicitation under such jurisdiction or to such person would be unlawful.
be used in any way for evaluating the
References
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Nazmiye Ceren Abay, Yan Zhou, Murat Kantarcioghu, Bhavani Thuraisingham, and Latanya Sweency. Privacy preserving synthelic data release using deep learning. In Machine Learning und Knowledge Discovery in Databases: European Conference, ECML PKDD 2018, Dublin, Ireland, September 10- 2018, Proceedings, Part I 18, pp. 510 526. Springer, 2019.
Gagan Aggarwal, Tomas Feder, Krishnaram Kenthapadi, Rajeev Motwani, Rina Panigrahy, Dilys Thomas, and An Zhu. Approximation algorithms for k-anonymity, Journal of Privacy Technology, 2005112001:400, 2005.
Mchreen Ahmed, Hammad Afzal, Awais Majeed, and Behram Khan. A survey of evolution in predictive models and impacting factors in customer churn. Advances in Dato Science and Adaptive Analysis, 9(33:: 1750007, 2017.
Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg. Structured denoising diffuusin models in discrete state-spaces. Advances in Neural Information Processing Systems, 34:17981-17993, 2021.
Matej Balog, Tlya Tolstikhin, and Bernhard Schölkopf. Differentially private database release via kernel mean embeddings. In International Conference on Machine Learning, pp. 414 422. PMLR, 2018.
Samah Baraheem and Zhongmei Yao. A survey on differential privacy with machine learning and future outlook. arXiv preprint arXiv:2211.10708, 2022.
Boaz Barak, Kamalika Chaudhuri, Cynthia Dwork, Satyen Kale, Frank McSherry, and Kunal Talwar. Privacy, accuracy, and consistency too: a holistic solution to contingency table relcase. In Proceedings of the twenty-sirth ACM SIGMOD-SIGACTTSIIG.RR symposium on Principles of database systems, pp. 273-282, 2007.
14

---

Published in Transactions on Machine Learning Research (06/2024)
Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman. Algorithmic stability for adaptive data analysis. In Proceedings of the forty-eightte annual ACM symposium on Theory of Computing, pp. 1046 1059, 2016.
Avrim Blum, Katrina Ligett, and Aaron Roth. A learning theory approach to noninteractive database privacy. Journal of the ACM (JACM), 60(2):1 25, 2013.
Vadim Borisov, Tobias Loemann, Kathrin Seßler, Johannes Haug, Martin Pawelezyk, and Gjergji Kasneci. Deep neural networks and tabular data: A survey. IEEE Transactions on Neural Networks and Learning Systems, 2022.
Andrew Campbell, Joe Benton, Valentin De Bortoli, Thomas Rainforth, George Deligiannidis, and Arnaud Doucet. A continuous time framework for discrete denoising models. Advonces in Neural Information Processing Systems, 35:28266-28277 2022.
Nicholas Carlini, Matthew Jagielski, Chiyuan Zhang, Nicolas Papernot, Andreas Terzis, and Florian Tramer. The privacy onion effect: Memorization relative. Advances in Neural Information Processing Systems, 35:13263 13276, 2022.
Nicholas Carlini, Jamic Hayes, Milad Nasr, Matthew Jagiclski, Vikash Schwag, Florian Tramer, Borja Balle, Daphne Ippolito, and Eric Wallace. Extracting training data from diffusion models. arXiv preprinl arXiv:2301.133 13188, 2023.
Andrew Carr. Diffusion models for document synthesis.
https:///retel..l//bb.
2022.
Fdward Choi, Siddharth Biswal, Bradley Malin, Jon Duke, Walter F Stewart, and Jimeng Sun. Generating multi-label discrete patient records using generative adversarial networks. In Machine learning for healthcare conference, pp. 286 305. PMLR, 2017.
Jillian M Clements, Di Xu, Nooshin Yousefi, and Dmitry Efimov. Sequential deep learning for credit risk monitoring with tabular financial data. arXiv preprinl arXin:2012. 1000002..3330 15330, 2020.
Graham Cormode, Magda Procopiuc, Divesh Srivastava, and Thanh TL Tran. Differentially private publication of sparse data. arXiv preprint arXi::1103.082: 2011.
Graham Cormode, Cecilia Procopiue, Divesh Srivastava, Entong Shen, and Ting Yu. Differentially private spatial decompositions. In 2012 IEEE 28th International Conference on Data Engineering, pp. 20 31.
LEEÉ, 2012.
Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans on image synthesis. Advances in Neural Information Processing Systems, 34:8780 8794, 2021.
Bolin Ding, Marianne Winslett, Jiawei Han, and Zhenhui Li. Differentially private data cubes: optimizing noise sources and consistency. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data, pp. 217-228, 2011.
Tim Dockhorn, Tianshi Cao, Arash Vahdat, and Karsten Kreis. Differentially private diffusion models. arXiv preprint XrXiv:2210. 0.9999 2022.
August DuMont Schütte, Jürgen Hetzel, Sergios Gatidis, Tobias Hepp, Benedikt Dietz, Stefan Bauer, and Patrick Schwab. Overcoming barriers data sharing with medical image generation: comprehensive evaluation. NPJ digital medicine, 4(1):141, 2021.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru- Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molccular fingerprints. Advances in neural information processing systems, 28, 2015.
Cynthia Dwork and Jing Lei. Differential privacy and robust statisties. In Proceedings of the forty- first annuual ACM symposium Theory of computing, pp. 371-380 2009.
15

---

Published in Transactions on Machine Learning Research (06/2024)
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryplogruphy: Third Theory of Oryplogrphyy Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pp. 265 284. Springer, 2006.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trendsø in Theoretical Computer Science, 9(3-4):211-407 2014.
Khaled El Emam, Elizabeth Jonker, Luk Arbuckle, and Bradley Malin. A systematic review of re-identification attacks on health data. PloS one, 6(12))22877, 2011.
Sahra Ghalebikesabi, Leonard Berrada, Sven Gowal, Ira Ktena, Robert Stanforth, Jamie Hayes, Soham De, Sammel Smith, Olivia Wiles, and Borja Balle. Differentially private diffusion models generate useful synthetic images. arXiv preprint arXiv:2302. 2023.
Shuyang Gu, Dong Chen, Jianmin Bao, Fang Wen, Bo Zhang, Dongdong Chen, Lu Yuan, and Baining Guo. Vector quantized diffusion model for text-to-image synthesis. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pottern Recognition, pp. 10696-10706, 2022.
Kilian Konstantin Haefeli, Karolis Martinkus, Nathanaäl Perraudin, and Roger Wattenhofer. Diffusion models for graphs benefit from discrete state spaces. ar preprint urXiv:2210.01549, 2022.
Frederik Harder, Kamil Adamczewski, and Mijung Park. Dp-merf: Differentially private mean embeddings with randomfeatures for practical crivacy-preeervig data generation. In International conference artificial intelligence and statistics, pp. 1819-1827. PMLR, 2021.
Moritz Hardt, Katrina Ligett, and Frank McSherry. A simple and practical algorithm for differentially private data release. Advances in neural information processing systems, 25, 2012.
Jamie Hayes, Luca Melis, George Danezis, and Emiliano De Cristofaro. Logan: Membership inference attacks against generative models. ar preprint arXiv: 7ae.07000077666 2017.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in Neural
Information Processing Systems, 33:6840-6857 6851, 2020.
Hans Hofmann. Statlog (German Credit Data). UCI Machine Learning Repository, 1994. DOI:
https///doi.rrg/10224433 wtt.:/ii..or11.244433/3. /44777777777
Emiel Hoogeboom, Didrik Nielsen, Priyank Jaini, Patrick Forré, and Max Welling, Argmax flows and
multinomial diffusion: Learning categorical distributions. Advances in Neural Information Processing Systems, 34:12454 12465, 2021.
Hailong Hu and Jun Pang. Membership inference of diffusion models. arXiv preprint arXiw:2301.09950 2023.
ItsSuru. Loan Data. Kaggle. DOI: httppr//ww..engg...om///ttttte/ tttta///ttttssuaaoaaaaattaaa
Ali Jahanian, Xavier Puig, Yonglong Tian, and Phillip Isola. Generative models as data source for multiview representation learning. arXiv preprint arXiv:2106.00 05258, 2021.
Zhanglong Ji, Zachary C Lipton, and Charles Elkan. Differential privacy and machine learning: a survey and review. ai preprint or 1284, 2014.
Zach Jorgensen, Ting Yu, and Graham Cormode. Publishing attributed social graphs with formal privacy guarantees. In Proceedings of the 2016 international conference management of data, pp. 107 122, 2016.
Krishnaram Kenthapadi, Aleksandra Korolova, llya Mironov, and Nina Mishra. Privacy via the johnson- lindenstrauss transform. arXiv preprint arXiv:1204.2606, 2012.
Ron Kohavi al. Scaling up the accuracy of bayes classifiers: decision-tee tree hybrid. In Kdd, volume 96, pp. 202-20 207, 1996.
16

---

Published in Transactions on Machine Learning Research (06/2024)
Kristen LeFevre, David J DeWitt, and Raghu Ramakrishnan. Incognito: Efficient full-domain k-anonymity, In Proceedings of the 2005 ACM SIGMOD international conference on Management of data, pp. 49-60, 2005.
Ninghui Li, Tiancheng Li, and Suresh Venkatasubramanian. I-closeness: Privacy beyond k-anonymity and I-diversity. In 2007 IEEE 23rd international conference on data engineering, pp. 106-115. IEEE, 2006.
Yang Li, Michael Purcell, Thierry Rakotoarivelo, David Smith, Thilina Ranbaduge, and Kee Siong Ng.
Private graph data release: A survey. arXiv preprint arXin:2107.04245 2021.
Yang Li, Michael Purcell, Thierry Rakotoarivelo, David Smith, Thilina Ranbaduge, and Kee Siong Ng. Private graph data release: A survey, ACM Computing Surveys, 55(11):1 39, 2023.
Yuting Liang and Reza Samavi. Optimization-bassed k-anonymity algorithms. Computers & Security, 93: 101753, 2020.
Zinan Lin, Vyas Sekar, and Giulia Fanti. On the privacy properties of gan-generated samples. In International Conference on Artificial Intelligence and Statistics, pp. 1522-1530. PMLR, 2021.
Kun Liu and Evimaria. Terzi. Towards identity anonymization on graphs. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pp. 93 106, 2008.
Kun Liu, Hillol Kargupta, and Jessica Ryan. Random projection-based multiplicative data perturbation for privacy preserving distributed data mining. JEEE Transactions on knowledge and Data Engineering. 18(1): 92 106, 2005.
Xucsong Lu, Yi Song, and Stéphane Bressan. Fast identity anonymization on graphs. In Database and Expert Systems Applications: 23rd International Conference, DEXA 2012, Vienna, Austria, September 3-6, 2012. Proceedings, Part 23, pp. 281-295. Springer, 2012.
Ashwin Machanavajjhala, Daniel Kifer, Johannes Gehrke, and Muthuramalrishman Venkitasubramaniam. I-diversity: Privacy beyond k-anonymity. ACM Transactions on Knowledge Discovery from Data (TKDD), 1(1):3-es, 2007.
Ashwin Machanavajihala, Daniel Kifer, John Abowd, Johannes Gehrke, and Lars Villuber. Privacy: Theory meets practice on the map. In 2008 IEEE 24th international conference data engineering, pp. 277-286. IEEE, 2008
Amy L McGuire and Richard A Gibbs. No longer de-identified. Science, 312(5772) 371, 2006.
Sebastian Meiser. Approximate and probabilistic differential privacy definitions. Cryptology ePrint Archive, 2018.
Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty- ninth annual ACM symposium on Theory of computing, pp. 75-84, 2007.
Nicolas Papernot, Martín Abadi, Ulfar Erlingsson, Ian Goodfellow, and Kunal Talwar. Semi-superrisedd knowledge transfer for deep learning from private training data. arXiv preprint arXiv:1610.0575. 2016.
Shreyas Patel, Ashutosh Kakadiya, Maitrey Mehta, Raj Derasari, Rahul Patel, and Ratnik Gandhi. Correlated discrete data generation using adversarial training. arXiv preprint 1rxi::1804 000.00925, 2018.
Yury Polyanskiy. Lecture on information theoretic methods in statistics and computer science. University Lecture, 2020.
Vamsi K. Potluru, Daniel Borrajo, Andrea Coletta, Niccolò Dalmasso, Yousef El-Laham, Elizabeth Fons, Mohsen Ghassemi, Sriram Gopalakrishnan, Vikesh Gosai, Eleonora Kreačié, Ganapathy Mani, Saheed Obitayo, Decpak Paramanand, Natraj Raman, Mikhail Solonin, Srijan Sood, Svitlana Vyetrenko, Haibei Zhu, Manuela Veloso, and Tucker Balch. Synthetic data applications in finance. aix preprint ar 20X.v:4401.0081,, 2024.
17

---

Published in Transactions on Machine Learning Research (06/2024)
Taherch Pourhabibi, Kok-Leong Ong, Booi H Kam, and Yee Ling Boo. Fraud detection: A systematic literature review of graph-based anomaly detection approaches. Decision Support Systems, 133:113303, 2020.
Alessandra Sala, Xiaohan Zhao, Christo Wilson, Haitao Zheng, and Ben Y Zhao. Sharing graphs using differentially private graph models. In Proceedings of the 2011 ACM SIGCOMM conference on Internet measurement conference, pp. 81 98, 2011.
Nicholas Schork. Personalized medicine: time for one-person trials. Nature, 520(7549):609 611, 2015.
Ravid Shwartz- Ziv and Amitai Armon. Tabular data: Deep learning is not all you need. Information Fusion, 81:84-90, 2022.
Alex Smola, Arthur Gretton, Le Song, and Bernhard Schölkopf. A hilbert space embedding for distributions. In International conference on algorithmic learning theory, pp. 13 31. Springer, 2007.
Gowthami Somepalli, Vasu Singla, Micah Goldblum, Jonas Geiping, and Tom Goldstein. Diffusion art or digital forgery? investigating data replication in diffusion models. arXiv preprint arXiv:2212.00 03860, 2022.
Latanya Sweeney. k-anonymity: A model for protecting privacy. International journal of uncertainty, fuzziness and knowledge-bused systems, 10(05):557 570, 2002.
Traian Marius Truta and Bindu Vinay. Privacy protection: p-sensitive k-anonymity property. In 22nd International Conference on Data Engincering Workshops (ICDEW'06), pp. 94-94. IEEE, 2006.
Allan Tucker, Zhenchen Wang, Ylenia Rotalinti, and Puja Myles. Generating high-fidelity synthetic patient data for assessing machine learning healthcare software. NPJ digital medicine, 3(1):1 13, 2020.
Dennis Ulmer, Lotta Meijerink, and Giovanni Cinà. Trust issues: Uncertainty estimation does not enable reliable ood detection medical tabular data. In Machine Learning for Health, pp. 341-354. PMLR, 2020.
Dinusha Vatsalan, Peter Christen, and Vassilios S Verykios. A taxonomy of privacy-preserving record linkage techniques. Information Systems, (8(6))946-966)) 2013.
Clement Vignac, Igor Krawezuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard. Digress: Discrete denoising diffusion for graph generation. arXiv preprint arXiv:2209.140 14734, 2022.
Jianian Wang, Sheng Zhang, Yanghua Xiao, and Rui Song. A review on graph neural network methods in financial applications. arXiv preprint arXte:2111.15967 2021.
Yu-Xiang Wang. Per-instance differential privacy. Journal of Privacy and Confidentiality, 9(1), 2019.
Yixin Wu, Ning Yu, Zheng Li, Michael Backes, and Yang Zhang. Membership inference attacks against Lext-to-image generation models. arxiv preprinl arXie:2210.0 000966, 2022.
Liyang Xie, Kaixiang Lin, Shu Wang, Fei Wang, and Jiayu Zhou. Differentially private generative adversarial network. arXiv preprint arXiv: 1802. 06739, 2018.
Jun Zhang, Graham Cormode, Cocilia M Procopiuc, Divesh Srivastava, and Xiaokui Xiao. Privbaycs: Private
data release via bayesian networks. ACM Transactions on Dalabase Systems (TODS), 42(4):1 41, 2017.
Shuai Zhang, Lina Yao, Aixin Sun, and Yi Tay. Deep learning based recommender system: A survey and new perspectives. ACM computing surveys (CSUR), 52(1):1-38, 2019.
Lin Zheng, Jianbo Yuan, Lei Yu, and Lingpeng Kong. A reparameterized discrete diffusion model for text generation. arXiv preprint Xrx::22302 05737, 2023.
Shuheng Zhou, John Lafferty, and Larry Wasserman. Compressed and privacy-sensitive sparse regression. IEEE Transactions on Information Theory, 55(2):846 816666666666 2009a.
Shuheng Zhou, Katrina Ligett, and Larry Wasserman. Differential privacy with compression. In 2009 IEEE International Symposium Information Theory, pp. 2718 2-22.. IEFE, 2009b.
18

---

Published in Transactions on Machine Learning Research (06/2024)
Appendix
Contents
A Proof of Theorem
21
Notations
21
Proof Sketch of Cheorem
21
Main Proof
22
B
Relaxed Conditions on 7) and c
24
B.1 Relaxed Condition on 1/1
24
B.2 Relaxed condition for c
25
B.3 Comparison of Original Enhanced Conditions for Data- Dependent Quantities
C Time Complexity of The Privacy Bound A Algorithm for DDMs
26
D Lower Bound pDP
26
E DP Guarantees of DDMs from pDP
27
F Details on Examples
29
Analysis on ger
2 Analysis on Th. c2
31
Experimental Settings
33
Datasets
33
Environment
34
Additional Sctup Configurations for Experiments on Real Datasets
34
Dalasel Preprocessing
H.2
Experiments on Testing Effectiveness of Privacy Bound Algorithm in Sec. 4.2.1
34
H.3
Experiments Membership Inference Attack in Sec. 4.2.2
34
Additional Experimental Results
35
Privacy Leakage and Behavior of Data-dependent Quantities under Various Noise Schedules
35
2
Most Private and Most Sensitive Points under Skewed Distribution
35
Main Lemmas and Corresponding Proofs
36
Proof of Lemma
36
2 Proof of Lemma A.2
36
19

---

Published in Transactions on Machine Learning Research (06/2024)
Proof of Lemma A.3
37
Proof of Lemma A.4
37
Proof of Lemma
41
Proof of Lemma
44
7 Proof of Lemma 0)
45
8 Proof of Lemma D.2
49
K Additional Lemmas and Proofs
50
L Specific Discussion on T(V), Vi-1, Vi)
56
20

---

Published in Transactions on Machine Learning Research (06/2024)
A Proof of Theorem 1
A.1 Notations
In this section, we introduce and recall important notations for the convenience of presenting proofs. Let Veja, (T), E (0,1} denote the intermediate data distribution
at time t trained with dataset. À in the forward q(-) and backward p(-) processes. Recall some notations μt = (k))a)) Mi = (1-as)/ke pt (k+))))),)//k Pr = = -1-oa)/kk R2 = PT //T R₂ = ptt /Pt and similarity 1im(V,, v",t) (",)=== -:)==vexx R R Let Nv,v') = lV E V1 s.t. @(v,v" I nH and (N,) = l E V s.t. @(v.v") = =ntl. Let lvşv', lv=v' denote the characteristic function over v and v'. Given dataset V, define Dill = (v Vilv = -).. Further, (++ (
Note that in certain cases, when there is no potential for confusion, employ a slight abuse of notation by representing intermediate data distribution r.V.S V x in its onc-hot encoding form, and we use M,(V) as shorthand for 1).
A.2 Proof Sketch of Theorem !
Characterizing Privacy Leakage with Expected Conditional KL Divergence. First, we leverage coupled KL divergence to quantify the inherent privacy guarantees of the DDM-generated samples. Given adjacent datasets Vo, Vi (1 [ Vi), the mechanism M, satisfies (e, -T-E-r)-- -DPP with respect to (Vo, v*) if DRL (MMM()))))MM(PP) + (MM.())))
I Note that the generation process V VT-IJ -.ua forms a Markov chain, and in order to keep track of privacy leakage from each step, upper bound the coupled marginal KL divergence by summation over conditional KL divergences. By leveraging sufficient training, backward path approximation (Assumption and 2 with conditional independence properties, we obtain
T
(utr s
Σ t=
+ 0(V7 +%)
(13)
where
B1 (
DKL (g(v Da
represents the expected coupled KI. divergence for each feature, conditioned on the data at time t, and
B2
E Baw.
describes conditional KL averaged over measure gap and can be directly upper bounded by -
Measure Partition to Compute Expected Conditional KL Divergence in B1. When quantifying D1, certain regions of the space x may have a large measure under ((Vejp), but a small DkL. gap, while other regions may exhibit the opposite behavior (illustrated in Fig 2 Thus, our objective is to partition the probability measure into distinct sets, with the aim of achieving a balance between the expectations of DKL. in each set (can be interpreted as achieving balanced privacy leakage). Such balance can be achieved by selecting two radius parameters n, T% E {0, (0.1...,,n) to partition the space according to the distances to v* and vo V1. We partition the measure ((Vejo) into the following three parts under different conditions of and v/c: (1) q(ve E Sa) quantifics the q(Vij) mcasure for points near v (within n)-bll) or those generated from dataset points close to v*. (2) q(v, E S₁) signifies the ((Vrj) measure for points that diffused from points in dataset Vi position distant from v* (beyond the n-blll) and are closer to some elements in Vi than to v by margin of at least 1/-- (3) q(v, E S.) represents the q(vij) mcasure for points that diffused from points in dataset Vi position distant from v" (beyond the me-ball), yet closer to any points in V than y with morn than v/- As adjacent datasets differ by element v", the privacy leakage in S, and S. is
21

---

Published in Transactions on Machine Learning Research (06/2024)
notably higher than in St. However, for larger datasets, q(v, St) often constitutes a significant portion of the original data measure q(Vejo)- This is because the likelihood of finding points in the dataset close to
v* within a margin of 1/2 is high, especially when v/ is small. We show that B1 has general data-dependent upper bound n/sw,, For v Sa, we can further improve the bound to n(ā=1 Tt)/((ppt Me (R R2 ]] Thus, we upper bound 1 as
n + gvve St) ni @k) Mb) + q(v. E Sc) g syr
B1 s g(v. So)
(14)
RG Rg
Quantitics T and The can be adjusted to balance the three terms on the R.H.S of Eq. 14 such that $ 1 2q(ve E Sa) शoं Finally, the data-dependent quantity of is introduced to give a more accurate
n.
characterization of q(v Sa). By selection satisfies Eq. 19 have q(v Sa) 2N Hence, by
gluing the pieces together, we completes the proof.
A.3 Main Proof
In this subsection, we provide a rigorous proof of Theorem The related lemma prools are deferred to Appendix []
Step 1: Charactorizing pDP with Marginal KL Divergence. First, we quantify the inherent DP guarantees of the DDM-generated samples using Coupled KL divergence.
Lemma A.1 (Characterizing pDP with Coupled KL Divergence). Given two adjacent dataset Vo, (1VV =\) and a specific time step Tu, if the mechanism Mr, satisfics the condition:
Dkr (Vo)l-MM..)) +
(T))llMrs T
(15)
then the mechanism satisfies (c, -- with respect to vVo.**).
From this lemma, we know that the pDP guarantees of mechanisin Mr, can be characterized by coupled KL divergence.
Step 2: Upper Bounding Marginal KL Divergence with Expected Conditional KL Divergence. Note that the generation process VTJa + Vr-IJA - Vela forms a Markov chain, and the coupled marginal KL divergence can be bounded by summation over conditional KI. divergences.
Lemma A.2. Given two adjacent datasets Vo, Vi (MoV(v* = Vi) and a specific time step Ta, consider the mechanism Mr, for generating m samples, we have
DKL(Mpp (Vo) (11) + (KL (Pi))l)Mr.(
n
E Σ
Sm
(16)
Step 3: Relating Backward Conditional KL Divergence with Forward Process.
Lemma A.3. Assume the denoising networks trained on Vo and Vi satisfy Assumption and Assumption we have for any E (1.2....,
Ev Dww.
AE(0.1)
Σ xe(o.1)
E Pww.
f((1)++++))))))))))))))) f2(r))
(17)
k0(4T., 1) 1., 17 ii
# "
where f(()))
22%,
and f2( = 2 log
. .
14 (T
22

---

Published in Transactions on Machine Learning Research (06/2024)
Step 4: Estimating Expected Measure Gap via Measuring Partition As Vol[v"} V1, we consider the following partition of original coupled conditional KT:
Σ AE (0 ==1
By Paw.e
(18)
= E (gg(eo)
By (Pk (o
(19)
For
L1. we
can upper
bounded coupled KL
terms E Prulalvi-pl
+
won.lalli-nnl//llavii... as follows:
Lemma A.4 (Upper Bounding Coupled Conditional KL). Given adjacent datasets Vol[v*] V and specific DDM, have
Σ
Ae(v.) (20)
where (v2)) is defined as
A 1 1+ C(11, V Vo,t)
B. (R + 1)(()) v v),1) + Ri- 1Re <(V,, v", vo,()+
log(1
1=1
such that C(V, v", Vo,() Evoev(R,) oo vo)) (e A ut - -7-1//1 and B, R -1 1.
Measure Partition. Now, we have demonstrated that the coupled conditional KT. can be constrained by (v:).. On the one hand, the magnitude of Av(v;) heavily relies on the disparity between the distances of (Ve, v*) and (ve, V1). When v, exhibits greater similarity to points in V1 (i.e., Evgev, W(v, Vu) < (V2,, Vu)), the resulting privacy leakage is reduced. Otherwise, the privacy leakage will be significant. On the other hand, if v is an anomalous point compared to the points in V1, the probability measure g(Vejo) around v is relatively low, but the privacy leakage remains high. Therefore, in the subsequent analysis, we perform a partition of the probability measure to strike a balance between probability measure and privacy leakage.
We partition probability measure q(Veo) as follows:
glve 8o) = g(ve: (1) V. is diffused from vo E Vo s.l. @(vo, v²) S me (2) v*) ne),
glve E Sa) = q(ve (1) is diffused from vo E Vo s.t. a(vo, > and (2) 3ve Vo, st. wlv., vo) s o(vi.v) 16),
e
g(vi Se) glvi (1) is diffused from vo e Vo s.t. w(vo.v*) To and Vv' e Vo stt. a(v., v() o(v.,v') v*) - m/)
In this case, g(v, E S.) and g(v, E S.) represent low-probability events that carry a higher risk of significant privacy disclosure. On the other hand, q(v, E Sa) corresponds to a significant portion of the probability measure but exhibits minimal privacy leakage.
According to the above measure partition, we introduce the following lemma to further bound (Ar
23

---

Published in Transactions on Machine Learning Research (06/2024)
Lemma A.5. Given adjacent datasets Vo, V1 and specific DDM design, we have
4 4N (v")
E g [ (lccv & min
(21)
where 12 SVe I+Sim((Vi.v Ei=l log(1 R -im(( +)m v*,++ .0+11
B.
Ar ue 10t - 17-1/14
and B, R and nn E (0.1,..,, and of f0, 1 n= } satisfy:
n m n
o-Nn)(v")
s-Nue(V) (v') log N Na (vi) + log(Ar Br 8th ((-1)
log (aat))mm( + 1 log n11 m((1-at)
T 2
-2
(22)
2log Ri
and for given T/, the corresponding of is calculated in Algorithm
As shown from the lemmaa that when (1 + ) is small, we will have more accurate estimate of privacy leakage. Thus, we select the smallest that satisfy the above inequality which are monotone functions on both sides and we select ef according to Algorithm 2 Also, we observe that (n, 0) is a natural solution to the above incqualitics, therefore, the fcasible set of above incqualitics not empty. Further, Eq. (22) a weaker
condition compared with Eq. (9) in Main Theorem We further relax this condition in Appendix B
more precisely calculate the privacy bound.
Now that we have the upper bound estimation for 81, we consider B2 where the mcasure around point v* can be nearly zero when v* is outlier point compared to V1.
For B2, differently from previous analysis, we can directly upper bounded expected KL term Ey (vy-(o(v)p) (ovg)))-(eea))))) (Pa Vall as follows:
Lemma A.6. Given adjacent datasets Vo. V1 and specific DDM design, we have
E (vv-((ttvan)-((vee))) (pllaaaavll (1110//110)))))
(23)
P(vejo E EQ)
(1 Me
p
1
14 p
R. Re-1
+
(1
(24)
8(8 +
F4
R4-1
n(1
2 PP(vjo E EQ)
Re-1
(25)
32
s2
where Ω = (v.lC(V,, Vz, v², > $) and 0:
(1 u!
_ (1
(1
R
x
Re-1
att
R
Summarizing the above results, we reach the final result
8(V6, v*) m
min (NNu+ctmeev)) (v))
1
n 8the
lt 32
+0 VT
co(vi +3)
[ (ell- e
(26)
TT
Main Privacy Term
Error Term
B Relaxed Conditions on 7, and o
In this section, we further elaborate dapandepn quantities of and ne and present weaker conditions that are less restrictive than Eq. 9
B.1 Relaxed Condition on ?
As described in proof sketch that we partition the mcasure g(Vzjo) into three sets S,, S, and S, where introduced ne and of that define the points that are close to v within nall and the positive margin that whether specific point more close to v than points in Vi by this margin. By balancing the
24

---

Published in Transactions on Machine Learning Research (06/2024)
privacy leakage the these three sets w.r.t their measure, obtain the relaxed condition for ne. Define (' m/6) = Nn, (v"))) (v")) and recall that 4p: = At B, 8 we have
Me K² log [logd'(no (1 ()mm)) + log sPt ) -2
(27)
2 2log
14
Na (v') o-Nu (v*)
where ke (0.1..... (P (Ve. vo) 2 n)) =
argmin (0.1.....))))) Ej=x (7)
Na 1a (v"),
P7 (t)(tt)) <
N J. For technical details, we refer readers to the proof of Lemma A.5
B.2 Relaxed condition for ot
We introduce the data-dependent quantity of to characterize q(v, Sa), which subsequently aids in the privacy balancing process. Based on the definition of Sa, we further examine the measure Vi stemming from points both within the m--ball and those external to it. Specifically,
((v, E S =v(; (1) Ve is diffused from Vo E Vo s.t. @(Vo, v*) S or (2) v*) S nt)
(28)
Ve is diffused from Vo E Vo s.t. ((vo. v²) S nt) v is diffused from Vo E Vo s.t. w(vo. v*) E [m. +1, mm. (V v') S m)
+g(v2, V2 is diffused from Vo E Vo s.t. (Vv. v*) 2 (1 m) + 1, S S1))))
(29)
To this end, improve the algorithm (Alg.)) with weaker condition than Eq. 9
(RIGHT) to directly
calculate parameter of given specific 77 and particular model design. Recall that (mpe Ns, (v (v*).
B.3
Comparison of Original and Enhanced Conditions for Data-Dependent Quantities
Original vs. Improved Algorithm Prrvithh-Privvacy
Original vs. Improved Algorithm- (1 +
Failure Probability (6)
Failure Probability (6)
10 10-
Skewness 0.2 Imme
Site Sdewwess 0.2
Improved
Sxxenaas U.4 mmp m
>xteet
Sueinness
Imprived
Skejeness Improved
Skewnness 0.7
Improved
Skeiness Improved
Skewwees 0.9
Improved
Skewness 0.2 Original
Skewwess 0.2
Original
Skewness Original
Seeweeess
Original
10-19
Skewness -0iriiala
Suewness 0.7 Original
Skewness 0.9 Original
Sse 0.9 Original
0.0
2.5
5.0
7.5
10.0
12.5 15.0 17.5
0.0
2.5
5.0
7.5
10.0
12.5
15.0
17.5
Each Diffusion Step (t)
Each Diffusion Step (1)
Figure 8: Comparison between two algorithms in each diffusion step (Linear Schedule): LEFT: Characterization of Privacy Leakage (Main Privacy Term). Right: Characterization (1 + c ).- Experimental Setup: Given specific DDM design &o = 5, n 5,T = 20, trained on dataset with = 30000 following skewed distribution with various skewness parameter.
consider fixed v* where each column has non-majority category. Data-dependent quantities are computed at each generation step based on 5 times independent tests.
In this section, we compare original conditions (Eq. g and improved conditions (Eq. (27 We detail the selection of (1 + of m alongside the privacy leakage observed at each diffusion step for various skewed distributions, as depicted
Fig. g Evident from the figure, the lines of lighter shade, denoting the enhanced conditions, are notably lower than their darker-shaded counterparts. This underscores the enhanced
algorithm's 's marked advantage over the original.
25

---

In this case, ny oं can be regarded as Published in Transactions on Machine Learning Research (06/2024)
C Time Complexity of The Privacy Bound Algorithm for DDMs
In this section, further analyze the total time complexity of privacy bound algorithm for DDMs. The total time complexity is O(s x T X n logn), n),, where represents the number of samples for which we aim to assess privacy, 7 denotes the total diffusion steps, and n is the feature dimension. The most time-intensive part of our algorithm involves selecting the radius (lines 9 in Algorithm [], where determining the radius coefficient for each sample at each diffusion step for a given requires (logg n) time through binary search.
D Lower Bound on pDP
In this section, we delve into the lower bound of pDP. Specifically, we examine datasets with one or dimensions (n 1,,,, and our findings illustrate the tightness of privacy bound in relation to dalaset size s, exhibiting order of Oz()). Our discussion will mainly focus two-dimensional case only have exchange of dimensional features in the generation process (due to conditional independence property) for n 2 2.
First, we introduce several diffussin--oefficciett based quantities:
/r F. C2
Hi Fi-1, Ct.e
Mt - C22
Me
pt-1 14
C₁
(30)
14
Pr
These quantities represent the values of g(vi-1lv vo) for any i E [n] across various combinations of vi-1 v/. and vg-
Theorem D.1 (Lower Bound on Inherent pDP Guarantees for DDMs for = 2). Assume the denoising networks are perfectly trained (re is negligible). Given diffusion model architecture design (far) (e(()) ) there exist adjacent datasets Vo. Vi = Vol (v*} with feature dimension n 2. For a sufficiently large 8, the mechanism Mo(s;) 1) will not satisfies (e, -DP with respect to (Vo. v*) for
+... .. Fr Fr-2Gr-11 2. (1+ R2 A)
log
1+
(31)
and for any
8 < G Fi + ... FiF PT-2OT-1
(32)
8
R2 where G G.
2(02 R2
F, C₁ (C1, C2,) and Á min, 22
Proof Sketch of Theorem
D.1
Consider a worst case adjacent datasots with two categories Vo
0
0
1
1
1
(8)
& probability vector over four points
), i.e. To oं R4. i-th dimension denote the
probability of generating i-th point respectively.
Lemma D.1. Given the same assumption and diffusion model design, Let ej, E (1,2,3,4 43 denote the vector with 1 in the j-th position and (ss elsewhere where the appears in the j-th row, we have
(
Te. 201 + F1G,2 + +.... FiFe Fr-2Gr-1
(33)
-0.1
(34)
26

---

Published in Transactions on Machine Learning Research (06/2024)
where Ft and G. positive diffusiio--coeffiiiett based constants
F. 4(1r A A + 4(s -6-
. E [T],
(35)
(s + 1)
R2 - 1)
G1 (1+ (s 1) R2)
(36)
R))
[ss - 1)((,,,-C2.)(11 )2 ( ) (21(422, 3(s 1), ( 2(s
- C2,1)(14
G.
,t f2, (2,...?T) T}.
[[s (sx 2(4 ]3][[[s 1) )a (pz }a}²
(37)
and
A = (s + 1) - [(s-
202.ll + 2C2,).
(38)
B (s +1 +) Ct. -
(39)
C (s+ [(s 1)) + 2C,, 2C2.)
(40)
Lemma D.I demonstrates that when datasets Vo and Vi differ by single sample relative dataset size of 8, the output measure of the diffusion model will exhibit difference of at least (2((2) in its predictions.
Lemma D.2. Given the same assumption and diffusion model design, we have
R (R + . A A- -
T S + To
(41)
where we have
min C2..8 8
RC
Čz.
Č
Ct. R2
Ei (8 (8-1) 1) Cia ( (8 (8-1)
C2t
C2 }}-
2
8 R +1
RR +1
$ R
s R
(42)
Lemma D.2 suggests that if a specific category constitutes approximately 1 of the original dataset, then, the diffusion model will produce data from this category at a proportion of (.))).
Therefore, consider the measurable set {[1,1]²} from Lemma D.1 and Lemma D.2 for sufficient large s, for any E N4, select
1+ (1+ G
FiG2 + .... F.. Pr 2G=1 c. c-(1+ (
60 = log
(43)
such that
8 (Mo 1) EB) - <PMoo(M(iV EB)
(44)
= -(P(MM (Vo 1) E EB) - PP(Mo(Mi: E B)) - (E 1)P(Mo(Vi:))
(45)
1-1 G1 Ci+FiG. F.G2 + F.F2. F1-2 =0,(t)
(46)
where G = R2
G
20 C2.)) F. = Ct. (C1, - C2,) and Ä = min, C2,
Let c = 2, we
R2
1
obtain the results.
E DP Guarantees of DDMs from pDP
In Sec. 2 we highlight the distinction between pDP and DP. The former prioritizes protecting the privacy of specific point with respect to (large) dataset, prior to training, proving beneficial for preprocessing datasets
27

---

Published in Transactions on Machine Learning Research (06/2024)
with privacy assurances. The latter, however, addresses the privacy implications of publishing model. In this section, we will discuss how to derive general DP guarantee for DDM from pDP by examining the worst-case adjacent datasets (Voliv*} = Vi). As mentioned in Sec. 3 the key for bounding the coupled KL divergence can be further focusing on balancing the privacy budget over three mcasure partitioned sets Sa, S. and S. ie.
n2 A. A.AA.B. Be + gVv. So)
q(v So)
q(v, Sc) 5
(47)
gVr
R Rg
We first consider the worst case for datendepnndent quantity th.
8th 1 Sim v log(1 1 +
n
A
B.
(48)
12_ Sim .²1() + Sim vz, +1
where A = no (4/t1/0t 1 ) and B,
R 1
From the definition of similarity (Sim), we observe that the worst scenario arises when vž an outlier within the dataset where, for each feature dimension, only one point in Vi shares the same overlap on that ==). From this, can further prove that the similarity Sim(V/, v", ,) 2
particular dimension (i.e. DDI Silv" ,v,1) 2 (m-1), Therefore, .yx is upper bounded by
(R,) n) + (n-1),,,), Sim()
1 8t + (R))))()- n) + (R,)2-n log(1 + R2= (R,)--n + (R,) ((a)-n(( "(8 n) + (ft,) +1
A
B.
(49)
denote
where the R.H.S I. is independent from dataset properties.
Discussion on Dataset Independent Quantity Vt, In the generation process, as we progressively transit from noisy regime (relatively large t) to noise-free regime (relatively small t), we have R₂ monotonically increases from 1 to 1+(k-1)a1 and v evolves from ( to O,(1). This aligns with the behavior of data-dependent quantity W1.
I-ai
Next, we consider the privacy balancing radius n, and c, Similar to the discussion in eh, we consider the worst case when Vž stands as an anomaly in the dataset such that for every feature dimension, there is a single point in V that coincides on that specific dimension. Under this case, the conditions for ne and of will be
log logh((n) + log(Ar B. Mc) )
).))
log h((1 + c))))) + 3
12 x- +
-2, c2
(50)
log 1 -1
2log
P.
where x² rrgminneeu.1.com (P (v vo) 2 x) 5 Natopm (v') s-N,,.v²)
} argmin ke(0.1.....t (E (3) (1-
Tt ( Na Na (v") N-N,, (vt) } and generalized h(n) = 8 (ncn+1) + (m=n-1) + (-00): 1 (n=n)-
Discussion on Dataset Independent Quantity Th, cT As depicted in Eq. (50). the conditions for T/ and et are data-independent. As diminishes from T (with ā. - 0 representing the noisy regime) 1 (where ā indicates the noise-free regime), the value of (1 + of ) transitions from to 0, consistent with those observed under data-dependent conditions.
Synthesizing the aforementioned results, we put forth the theorem detailing the inherent differential privacy guarantees of DDMs.
Theorem E.1 (Inherent DP Guarantee for DDMs). Given any adjacent dalasets Vo, Vi. Assume the denoising networks trained Vo and V2 satisfy Assumption ! and Assumption D Given specific time step Ta the mechanism. Mr.k; m) satisfies (c, (2,5)) -)differrennti privacy such that
8(Vo v²) S m
T
min
4N (v")
s 1
n
net o
(v++t)) F ]((11 - -e
(51)
3²
Moin Prieucy Term
Error Term
28

---

Published in Transactions on Machine Learning Research (06/2024)
where L Mi, 2 diffusion coefficients-based quantities such that (īe, satisfy Eq.
50
V
solisfies Eg. 49 and 0 M (TTPi//) 1/) + Pe PT1// (1 - Re/ 11-1).
F Details on Examples
In this section, we provide detailed analysis on the examples presented in Sec.
F.1 Analysis on gP1
Proposition F.1. Given a skewed distribution with parameter p. Let v² be a non-majority point and Vol \ (v*) (1
sampled from the distribution. Define Tt probability
k-
1-p
+
R.
Pe
(D) When = wn (,(p)))) ) we have with high
(o4-1 01e 3 (kplt Pi:
(52)
g
R T8
2n-1 + nn
Proof of Proposition F.1 Recall the definition of 1 g
1
A 1+ Sim (V, v t) log 1+
B. R Sim Si (ViV" vv't) + Sim(V), v*,t) +1)
(53)
8/4
where As = ut (M/1/pt p and B, R 1.
Given V E V
non-majority point, sample E Vi from skewed distribution with parameter
p. Thus, we have a(v", v) follows binomial B(n, 1 - ) distribution. Therefore, E
(( Mi
((" ( w)
Eien (1t ( (0)
())) - #i m (1 1D))", and thus E(Sim(V1 v,t)) 1
17
BBE VEn Mi ((v)))))))) Mil ( #1 b))) (1-1)))) = -B1l (T
1- Dya (1 1=)) + k Let Eg ==
H + de
}) = (1 (1 + +
Since max _ j M) - min 0(v v) < 1, from concentration inequality, we have for any small e(e Ex),
FO Sim (V, v", 1) IEiim(, v0] |0) 22xxp( 2exp(-22es)
(54)
Let = é' E.. Thus, with high probability at least - 1-2eep((2(())) (-2(')) we have
Sim(V,, v 1) [E, e, E, + (B,)
(55)
Now, we consider Sim ti v*,(), let X X X be Bernoulli random variables such that
j-th sample vl) E Vi such that (yli) = vi
xj 0. otherwise.
(56)
From Hoeffding incquality, we obtain
1 P(1
X
X1II 2 G)) 2(x)(()((())
(57)
j=1
where El3 Σj= X3] = 1 Let of
1-p ट). Therefore, have with high probability 1- (cxp(-2(1-11)) k-
()
1 1-P E)s,, 1- P
Σ Xj E
k 2
(58)
1-1
29

---

Published in Transactions on Machine Learning Research (06/2024)
Let N, = = |/lv" = Let Y1, Yi,..,, Yi, denote the features of points in Vi v on dimensions other than i-th dimension, which can be viewed as random variables sampling from categorical distributions with dimensions. Recall that (v, wvv Ivigve. Hence
N₂ = j=1 14
Sim Sim
(8,x*
(599
Similar to the derivation of Sim(V), v², we have
E
14 ) (0..0))).0))
Σ
n-1
-
1
1 P n 1- (1
1 (1-10 --))) ))² '
(60)
He
i
k -
k- - 1
1=0
Pr
1 - 1)= =: E
(1
(61)
k
14
k:
Applying Hoeffding inequality, we have
1 P(1, Sim() ,V",))- - ( k-1 u4
1 - P 11
1 1- )) 1 (2) S 2exp(-2(c))
(1)
(k (1- k- -2)s)
1 1-P
+
(1
(62)
N₂
k k-
where (i) is because max( Hi -- 3(,(0,,')) - < and the concentration property of N, Let
14
be = I " (1 )))) "- Z Summarizing the above, with high probability (1 -2exp(-2((F)) (2))2.
s1 exp( 22 (2))2.s)
1 V t) E Ej 1-p
k- (1 (1- E; 1- h- (1 (1+ + +
(63)
Therefore, in order to let Sim Si (
v", t), E [n] and Sim(V) (1, v", t) to concentrate, we require as E + 0,
p: (1 (1 I 2exp(-2( s) 2 expp( 2exp(-2 k-1 -
+1. +1
(64)
Thus, - [n] and exp(-2(c)) = (1). Define n. : - + - (1 (1-
=
M
From above, we obtain the condition wn (ogg)) Here, we list a sufficient condition for n to satisfy the :
constraint: n can be chosen as n = l-a log for any positive a <
2 log
B. R2_ Sim ( .v" Sim (V v+ ) when = wn
A For 544 - En VI log 1+
log 7.
with high
probability we have
A B,
(65)
R2_1 (4 --+))=))) + + pn 1 + pr
(5t (1- + B2
From the analysis above, we note that as the skewness of the distribution intensifies, the above term exhibits a monotonic increase with respect to p. This implies that the average distance between points in V and v grows, Icading to heightened sensitivity at point v*. Consequently, the privacy bound increases.
Note: From the aforementioned derivation, taking the logarithm of both sides implics that, since s = waa 1 )
with high probability,
R$
P (1 b
A. kD + pn 1 + Th (1 -1:) + 1=P)2n
1 2 2+ log,
+ 0.
(66)
A. B.
Thus, Vi2 2 as 0o.
30

---

Published in Transactions on Machine Learning Research (06/2024)
F.2 Analysis on m/. c..
Proposition F.2. Given skewed distribulion with porameter p. Let v² be non-majority point and Vo Vo\(v") sampled from the distribution. Define Tt = t- +
ni 1- When wa(C
b 20m h-)) -2(1)22111100 2)n logn) for some (x-2-p' 1), we have with high probabilily,
log( poo(n) - 1) + max
log( Pe. -
+ C.. -c.0)-2200
1/: = argmin nE [[en] monm)
n/n
(67)
log
2 2log Re
n(1-A;))
log(
log 2c
0
d argmin
dc
De
(68)
log
60 M-
P4
where pia(t) is the CDF of Binomiial distribulion with parometer 1 A. = -ut (ft-2/ -1-1//5) and B, = -
1 and Ct
log log it.
2 log Ste
Proof of Proposition F.2. Given v E V as non-majority point, and V1 are sampled from skewed distribution with parameter Consider specific mes G, the probability of failing into the ne-ball of v* is P(v; v*) S n)) E (2P P) S min((E=))" (en)"".1 1).
Now consider the following incquality:
log (Tt)
log (m)) + log Pt 2, -2 o
1 log 0((1 + c.) + log 2e
2 log n(1-x²)
+ max
(69)
2 2log PT
log
where I(nc) (s Ny, (v.(vv)))/N (v*), Ar St. To begin with, first consider ((n:) Nor 1. Let X1, X2, ... Xs. be the indicator random variables of whether the point in V fall in the -all of v²; i.e.
1, with (v follow skewed distributiion 3(v, v*) S Sn)))
X = (o.
(70)
0, with 1 - Plv: w(v follow skewed distribution; @(v, v") S n)))
Define (m)) Pvv;W(v follow skewed distribution; (v, v*) S 11))). Since Xim, are Bernoulli random variables, from concentration inequality, with high probability 1 - 2exp(-2((e) Pmn (m))s))
No. (v*) E ppm (n.) (1 - e'), pi) (1 +
(71)
Let E e' PT)())). Since (in(
define E1
Pin P we have with high probability
Pe
- 2
(ne) Piu (Tn(
61,
+
(72)
Pin (nt)
Similarly, define 62 P with same high probability,
log (m)) E log (T)) -1)
-1) +e2
E2.
(73)
1 From the analysis on 0.1 define (p,t))
A.B. + RG. F
There exist ex such that Es + as e' 0. Further
define 64 = T-(14 2 Jeg we have
1/2 log E 2logs - c,. 2og + 64
(74)
31

---

Published in Transactions on Machine Learning Research (06/2024)
Let c" log A.)
log fis
c1.
Then, from above, we have with high probability []
2 (exp(-2(ee) Pin (11) [s]{?
log( (1))
1)
log(
1)
+ C.. 0 -2-- c"
fe(m)) 2
max
(7))
(75)
log n((-117)
2 log Rr.
fe(me) -
log( Pim (1m()))))
max
log(
Pin (T+)
1)
+ +c+0
(76)
log ml1-H5)
2og Rs
where C ==
(..((A.)B.))
log log Ri
2 log Hr
In the proof Lemmna A.5 we already show the existence of ' that satisfy the condition i 2 [(m)). When (7:) wi
logg), ) we have the concentration properties. Since Pmn (m)) is strictly and s wn( -."
monotonically increasing with Th and 17t 2 en, thus, we need Pin (in((e ws (+)). Thus, we require
Wh ( Pー
1- P)
2cm - P 2(1 2(1-c)n
(77)
Therefore, when the above condition satisfied, we only require
log(
1) + max
log( Pin (rn) 1)
1/
Pio (m).
+ C₁, . -2, n [[e
(78)
log m(1-A])
2 log Rs
(87 A-m (mn)
where Pio E
(1 l.
One direct observation from above is that
In noise free regime (t close 0, i.c. āi - 1), we have log m(1-at) log Rd - oo and C. + 0. Thercfore, 1h2 O.
In noisy regime (I close T, i.e. az -> 0), similarly, we have log m(1-57) log 1, log Rd -> 0, and C. + co. Therefore, ?)
Now, we consider how skewness parameter p influence the selection of me Given fixed diffusion coefficients (aeheeT) with or monotonically decreases from to 0 f goes from to T. Given relatively large (neglect the influence of concentration error e"), and corresponding that satisfies w, (max(log 2mn 11 ([(1-t-)) - 2cn (1)))))))1)0))) ( -(11-())))))) We have the following observation: When we increase
the skewness of the distribution, fi 1-pm (mx) will increase monotonically with such that n, will increase
to n faster. In other words, given two skewness parameter p.p' with >>p', we have Tp 2 nH where of of denote the minimal y) that satisfy the constraint under two skewness parameters. Similar derivation can be applied to gi 1-pm and we obtain the results for ct
Proposition F.3 (Sufficient Condition). Given skewed distribution with parameter p. Let v be non-majority point and Vo' [v sampled from the distribution. Define T = + When = w, (1 ス -211 2)1-c)n logn for some e (x--5 1), the sufficient conditions of nh ot that satisfy Eq. g are
n log 8
-ma )/ log Rs
TJ 2
kj. P.
(79)
2 2 1 1-p
log max mp,
1}) +
32

---

Published in Transactions on Machine Learning Research (06/2024)
log
12
7h
2r
e/i
(80)
7/
log
k-1
log
p
Proof of Proposition F.3. From Proposition
F.2
when
= wni(la(1 1=1) 2on (1=P) 2(1 ))),, we have -
Tbe G from Eq. 68). Further since
Pin (m:) 2
P
n
7tt k - 11 ym m (1
" )
1 -
1 - P yM
(81)
k:
1: 1
k=0
From c c k-2-p'
1-p
we have
log( (1)
1) Sn log(
+ ne
(log
7
log
1
+ log
(82)
1-
1/2
p
k k-
s(n- 11) log(
(83)
1-
Therefore, the sufficient conditions of t/e and of will be
(n 1/1) log( $
(n- 11)) log( k=1
+ +c,, +c,0
+ max
(84)
log n(1-
2log Rr
log( 1-1) )
(1 + 67) log(
k-1) log 2e
1-p)
(85)
log P,
1
Further simplify the above terms, we get
log(
log Rs:
kjj
2 n
(86)
2 log
log (max
13) +
mp.
n-m
log
n1 17t
2e
A/4
G 2
(87)
1/
log
k-1
log
1-p
G
Experimental Settings
G.1 Datasets
In this section, we briefly introduce the real dataset included in the paper.
Adult (Kohavi et al.) 1996). The Adult dataset, also known as the Census Income dataset, contains information collected from the 1994 US Census Burean database. It serves the purpose predicting an individual's income category (above or below $50,000 per year) based on demographic attributes such as age, education, occupation, and more. With around 32,000 records and 14 features, is widely used for classification tasks.
German Credit (Hofmann, 1994). The German Credit dataset, curated by Prof. Hofmann, encompasses data from 1000 individuals seeking bank credit. Each entry is characterized by 20 categorical / numerical attributes, with labels as either good or bad credit. risk based on these features.
Loan (ItsSuru). The Loan Status dataset consists of 500 unique entries, each with 11 features. These records capture customer interactions with a bullet loan product. Labels within the dataset indicate whether loan was approved or not, making it suitable for classification tasks.
33

---

Published in Transactions on Machine Learning Research (06/2024)
G.2 Environment
Experiments were performed on server with four Intel 24-Core Gold 6248R CPUs, 1TB DRAM, and eight. NVIDIA QUADRO RTX 6000 (24GB) GPUs.
H
Additional Setup Configurations for Experiments on Real Datasets
In this section, provide additional details regarding the experiments real dataset in Section 4.2
H.1 Dataset Preprocessing
Adult. The original Adult dataset consists of continuous or discrete features. In our setting, we have selected the main features, namely: age, workclass, education, marital-status,, occupation, relationship, race, gender, hours-per-week. We have performed interval partitioning on the continuous features and merged some multi-category features (e.g., education) into single category for discrete features. As result, the number of categories for each feature does not exceed 5.
German Credit. The German Credit dataset is comprised of 20 features, both categorical and numerical. For our study, we focused on 10 primary features: status of existing checking account, duration in month, credit history, purpose, credit amount, savings account / bonds, employment, personal status and sex, age in years, job. We categorized numerical features, ensuring no category contained more than 5 subdivisions.
Loan. The Loan dataset encompasses 11 features, both numerical and categorical. In study, we incorporated all these categories and further segmented the numerical features into categories, each containing a maximum of lour subdivisions. The specific features are: Gender, Married, Dependents, Education, Self Employed, Applicant Income, Coapplicant Income, Loan Amount, Loan Amount Term, Credit History, Property Area.
H.2
Experiments on Testing Effectiveness of Privacy Bound Algorithm in Sec. 4.2.1
H.2.1 Denoising Network Architecture and Training Procedure
We designed a four-layer MLP equipped with 256 hidden neurons. Throughout the architecture, batch normalization was integrated, and the leakyReLU served the activation function. For consistency during training, we anchored the random seed at 123. The denoising network underwent training via the Adam optimizer, set with learning rate of 1e-3 and a weight decay of 5e-4. Our approach involved uniformly sampling the diffusion step and drawing batches of 30 samples each. The training spanned 100 epochs, focusing on minimizing the binary cross-entropy loss.
H.2.2 Evaluation via DownStream Tasks
To evaluate the efficacy of DDMs, we divided the original dataset into three segments: training, validation, and testing, adhering to 8:1:1 ratio. Leveraging the trained denoising network, we generated synthetic datasot, ensuring the number of instances for cach class mirrored that of the original dataset. We then engaged in downstream binary classification to measure the utility of the DDMs. In this context, we trained an independent MLP classifier using the synthetic dataset and subsequently evaluate its classification performance on the test set (original dataset).
H.3
Experiments on Membership Inference Attack in Sec. 4.2.2
H.3.1
Discriminative Model Architecture and Training Procedure
The discriminative model designed to overfit the data released by the target model, which indicative of the training data. We implemented a MLP for classification, fcaturing threo-layer architecture with each layer containing 256 neurons. The model leverages the ReLU activation function across its structure. The
34

---

Published in Transactions on Machine Learning Research (06/2024)
network's training process is guided by the Adam optimizer and the learning rate is adaptively adjusted, starting at 0.01, to optimize performance during training. The model iterates up to 1000 times until the tolerance level of 1e-6 is reached.
DData-dependent Quantity
Data dependent Quantity (1 c'
Privacy Leakage Generation
30-4 10'
Fallars probability (8)
800
150 Each Diffusion Step (t)
150 1855 Diffusion Step
Each Dirfaston Step
Figure 9: All based on single step-t term in Eq.main (Sigmoid Schedule): LEFT: Characterization of 20y MIDDLE: Characterization of (1 4 m. RIGHT: Characterization of Privacy Leakage (Main Privacy Term). Experimental Setup: Given specific DDM design 5, n 5, 20, = 10 trained on dataset with s 1000 following skewed distribution with parameter p. We consider fixed v² where each column has non-majority category.
Data-dependent Quantity 2
Data-dependent Quantity (1 +
Privacy Leakage in Genoration Process
Fathura Probability (8)
10
10-
10
0.5
2.5
5.0
7,5
10.0
123
15.0
17.5
150
2.5
5.0
7.5
150
12.5
150
50
7,5
150
125
15.5
17.5
Each Diffusion Step (t)
Bach Diffusion Step (1)
Each Diffusion Step (L)
Figure 10: All based on single step-l term in Eq.main (Cosine Schedule): LEFT: Characterization of MIDDLE: Characterization of (1 (1+00 o )r RIGHT: Characterization of Privacy Leakage (Main Privacy Term). Experimental Setup: Given specific DDM design & = 5, n = 5, T = 20, = 10 trained on dataset with 1000 following skewed distribution with parameter p. We consider a fixed where each column has a non-majority category.
Additional Experimental Results
In this section, we present additional experiments backup our main results in Sec.
I.1 Privacy Leakage and Behavior of Data-dependent Quantities under Various Noise Schedules
In our experiments, we assess the privacy leakage and the behavior of data-dependent quantities vi,, The and ot across different DDM model configurations. In particular, explore two additional noise schedules: sigmoid and cosine (defined as ā. = f(0)
f(O)* where f(t) = cos (1/T+e
1+s -/ The outcomes, depicted in Fig. 9
and Fig 10 resonate with our theoretical findings. It is observed that under all noise schedules, the privacy leakage intensifies for distributions that are more skewed.
1.2 Most Private and Most Sensitive Points under Skewed Distribution
Next, we delineate the evolving trends of the most private and most sensitive samples the skewness parameter shifts, providing insights into its impact on privacy leakage. We specifically focus on three DDM configurations: n = 5, k = T = 20, n = 10, k = T = 20, and n = 20, k = 5 100. For each setup, we adjust the skewness parameters p and curate the dataset Vo in accordance with the respective distributions. The most private and sensitive data points, based on the privacy budget, are illustrated Fig.
35

---

Published in Transactions on Machine Learning Research (06/2024)
Most Private Sensitive Sample
Skowness
As evident in the figure, escalating the distribution's skewness boosts the privacy budget for the most sensitive points (represented by dark-colored lines). Conversely, the privacy budget for the most private points (depicted by light-colored lines) diminishes. This observation consistent with our theoretical analyses: for highly skewed distributions, points distant from the main cluster exhibit reduced similarity, leading to augmented privacy leakage. Meanwhile, predominant points benefit from enhanced similarity, resulting in diminished privacy concerns.
10 10 (
Failurn Probability
5,20 butt Mott Semitre
10 1920, Nast sepatiss buir
A- 1.r in Mea Placte Poxt
0.3
0.5
0.7
Skowness (p)
Figure 11: Privacy budget trends across DDM configurations with varying skewness.
J Main Lemmas and Corresponding Proofs
J.1 Proof of Lemma A.1
Proof. To prove the pDP guarantee of DDMs, we seek to a stronger notion termed probabilistically differential privacy. First, we present the definition of (e, p--robabilistucalll differential privacy (PDP).
Definition J.1 ((c, Probballiaaalll Differential Privacy (Meiser 2018)). A randomized mechanism M: D + R satisfies (c, brbballrbballltttcaallllyy differential private if for any adjacent datasets Vo, V/2 E D and there exists sets Oo S rragg(MM where P(M(V)) S Oo) s 6, such that AA S range(M), we have
P(M(V)) E (V) S (AMMM))OOOO)
(88)
The following lemma connects the relationship between PDP and DP.
Lemma J.1 ((e, 6)-P to (c, 6PPD) (Messer 2018)). randomized mechanism M satisfies (c,8)-PDP, it also satisfies (c, 8)-DDP with respect (Vo, v*).
The following lemma further characterizes PDP with KL divergence.
Lemma J.2 (Characterization of (e, 8DD with KI Divergence (Lin et al. 2021 ). Given two adjacent tabular
datascts Vo, V1, consider mechanism M, let To and oं denote the probability measure of M(K) respectively. there exist a constant J such that.
(TL m1) + DKL (=]l== ST
(89)
the mechanism M satisfies (c, (G -) >-robabbilistic differential privacy for all 6 > 0.
J.2 Proof of Lemma A.2
Proof. First consider generating a single sample. In the generation process, VTJa + VT 1/A + .... Vela +
VTalA forms Markov chain. First we consider (vc.lo/(V:iolllleo(....l
DKL (V..oooV
(90)
(1)
< DKL (po (Po VTa+ VT Vro)llPo(VTall VT. Il..... Vr(1))
(91)
Po((r))) Po((T)))
log (v \
Ep (vr, -10. vo
(92)
P po vep))
Pol Po(VTTO) (vr11))
Pe (V Vejo)
Σ pol77p)pe(v7--nooy7)) ... (. vol
log
(93)
pd (v Ve(1)
VTA VT
t= Ta+1
Psl ( 1 Vajp)
(188)
Σ
Σ po(V II ps (vi olv
Σ log
(94)
Psl ps P=(v Veji)
36

---

Published in Transactions on Machine Learning Research (06/2024)
T
-DKalPalVroolllss +
Σ T=+++
Σ
Eumpo(veo) (Pol Pirp
= v))pp((i-in Vij =))]
(95)
where (i) follows from Lemma K.1
(ii) leverages Markov property and (iii) is due to conditional independence.
When generating m independent samples, consider the coupled sum and we prove that
(xI(Mr (2))l + Ma (V.)
(96)
Sm
Σ
E
Σ
(97)
J.3 Proof of Lemma A.3
Proof. According to the generation process, from Lemma
K.2
we know that for any E {0, 1}
Po Po(Vi-uxllMa))
Σ (ol v. ve
Mi 1T-11
(98)
14 14
Vola
Mi P
Define [1(x))
12.,1) 2oo
3t. We have
Me 1i 14e-1
A1(0.17
(1)
BvINg(M Prw f2(5x)
(99)
xE{0,1}
(4))
Ev
fi(1)) + f2(f))
(100)
A1fo,13
where (1) from Assumption 2 while (it) owing to Assumption 1 and Lemma K.3
J.4 Proof of Lemma A.4
Proof. To begin with, we first calculate q(vi-11x vi-1. Veja vv) and g(ve v.). 10.1).
q(vi- Vi- VeJa v.)
(101)
1
Σ g(vi-11 =V/ VI volvolA = vo)
(102)
-I2al
voEV.
a(VeJA VILV--IA = vi_1) a(Vc-111 = v = v())
1
a[v = v//vjj = -V/_)
(103)
q(V.jA- = v = =v()
VoEV.
(xt) (MT) fop (يit ) - (AT_1) ) Jui_ zng
Il q(ViJA = v\ voja = v/-1)
(104)
-PaI voEV
(mi.) vi-v (ft,)) vyjjng
1-1 1yte (#, t -1 (1rtt 1) 1-1 yy 1 (fT. 2 unb)
1
Σ
(1+))
(1it (
(105)
IVA
(pt) viru (ite ) Jujjen
(1, - w(vo.v.)
VOEVS
denote as r(vi vi vi
Similar derivation for <(vijp = Vt), we obtain
<VHjA= v.) PVAl
Σ
(n jol (o(vo.v))
(106)
VOEVA
37

---

Published in Transactions on Machine Learning Research (06/2024)
Now, consider the coupled KL divergence:
DKL
+ (KL( wanpoii--nnaallllvv---oo.
(107)
2(vi-110 ve)))
Σ v - = vi-1lv log
(108)
q(v -vi-1
q(v 1-1 v V2j0)
+ log g(ve11)
q V vi-1lv(11))
log
(109)
q(v) q(v) 1-111 = v V(j1)
((Vep)
<v =vi-1- vijo)
Σ (g(v)-110 = v, vv=o) - v(vi1111 = log
(110)
(v t-111 =vi-1+ Vi(1)
(1)
(s+1) q(v2 vt 1|0 =vt-1- Vgjo)
10 1o(v 1-100 = v= =(v( = vi-1l
max log
2
s q(vi (-11 -v Vipa)
( 1) q(vi = vi-1: Ve1o)
min log Vi-1
(111)
q(Vi-1111 vi-1 Vej1)
(Vun) is independent of vi-ij A E {0, 1} and (ii) is from Lemma K.4 where (i) is due the fact that log ((vija)
Before we dive into specific terms, r(yoit wx)) and k(v"), vo, v/) r(vg.vf ..1)) (Bi)" ylon " Discussion on specific values of T(m" D89)
define two terms for simplicity: <(v") vó. vi vt)
r(v", 189) R,
x(v), vi-n v)), va, vi-1 vi) and n(v"), Von v v() are presented Appendix
(vt For any ve X",
Now, consider the term log sq((v 211 Non
(s 1) q(v vi-1, V:jo = vi)
log
(112)
8 :((( v2-1 Vaju = v.)
log
1+
(113)
T(V vi) Σvgev, r(v" [ (4, (v) (( jalvov)---
=log 1
(114)
=(vgiv/_,,n)) E F(v" (.))
Denote Zi(Vo: v., v.) = (R (Vo.v))= Mi)) where (_,(v, = Ej= Lvizer = =[V. v) - Iviyve.
cl For simplicity, we shorthand Zi(vo: v.) as
V= vv)== (ulv-vv we)) R.
(i(.)). We have
(++1) 1): g(vl ([vi-1100 = v vejo vajo= =
v.)
log
(115)
svq(v =Vi Vi|1 vv)
Yol1 = =v)) 1 (8+1) ( ((vi_ = v Vij0 = v.) - 2. = Vol1
log
(116)
8 s.9(v = Vaj1 = =v:)
log
1 Eveer, R(v*i vy v v vz)o)(vo)
(117)
=log
1
Emseii R(vri, v/ vi_,, z Evernis R(v") vo. (.))),)))
(118)
38

---

Published in Transactions on Machine Learning Research (06/2024)
Observed that if vi-1 vni, R(v", Vo. v() 1 or RT-11 If vi-1 v2, R(v") vi- vi) or R1-1. According Appendix log (++1) -i - -
vi
L we have the following qualities for the maximum and minimum of
(s + 1) g(v vi-1 Vejo vo)
(s 1) g(v t-10 v Vejo vej== vi)
max log 8.Q(V2_111 Vi-1 =v)] = =log sv v", Vej1 vt) v/
(119)
=log
+
(120)
E Evoeni.y Zi(vo) + R EvoErhyAAve Zi(vo)
V Veju vo) (s + 1) g(Vi-1jj vi-1 Vejo vi) (s + 1) -VV--vju V2-1
min log
log 8 g.Q(V, =V Vej1 = vv)
(121)
E(A!
q(V = V Vol1 = =v))
llog + RI-1 EvoEViNG 2i(Vo) + EnDevivgruth Zi(vo)
(122)
where v argmax
E(W)(m ( EnoEMing=vv (i(.)).
Now, we consider max, log (++1) (=+1)
s-q(r; i11 " min log ,g(iv =
(++1)-q(vi11) q(Vi-110 = v Vijo)
(s+ q(v = - Vejo)
max log Vi-1
min log Vi-1
(123)
8. 8.9(vi-111 = vi-1. vel1)
8 &.9(v' = Vi-1. Vil1)
llog
1 EvoeWing=-" Zi(vo) RT-1 EVDEV Zi(vo)
- log
1 +
(124)
Re-1 EvoEVi Zi(vo) EvtEn. 2 (v()))
Evoening-vn 2i(vo)+ SoDEiiNgu 2i(vo)
=log 1 +
(125)
E Enger -f 7((vo)+ EnDEV 27(vo)
RI-1 1 Exj=vi" Zi(vo) + Evgeevi Zi(vo) - Evj=v' Zi(vo) - -R,,, E Evgeri Zi(vo)
log 1+ EEvi=v' Zi(oo) + RT Evieen.r Zi + Ri-1 Evi=viz, Zi(vo) + Evi (vo))
(126)
where in (i), we have omitted the summation constraint Vo E V1 for brevity.
Further, we split Everve Z((v)); Eveerei 7i(Vo) two terms as follows:
Σ 2i(vo)
Σ
Σ
(v(v))
(127)
viEvi
Σ
Z((v)) =
Σ
ZVvo)= +
Σ
(v(v))
(128)
vd=
virvi
Plugging back the split terms into Eq. 126
we get
(s 1) g(v] (1110111000 = v Yejo)
(s+ 1): g(v] g(vi-110 = vi-1 Vujo)
max log vi
min log vi
(129)
q( =V/-1, Vij1)
q(( =V/-1, Veji)
(a - 1)((a + 1)y + 2]
=log
1+
(130)
(ax + y + 2)(ay + x + +2+1)
39

---

Published in Transactions on Machine Learning Research (06/2024)
(8) (
(a - 1) + 1)
- log 1 + (a² + 1)x ay + az +1
(131)
(R 1) +1)
=log(1 +
(132)
(R +11 +11+11 = Zz(v)) + R4-1 E vv/=v (voo + .R-1 Evieri Zi(vo) +
(Ro-1 1)( R +
I <og((1 +
(133)
(R2-) (1) ((V)) .V, v2, R2 1 Ro ((1/V) +
(R 1)( 11)
Slog(1 + (RG-1 + 1) <(V) .v' vo.)) Ro-1/Bo C(V, v", vo, +1
(134)
where we define a = R
Eveer, v/= (vo),,y
Vioevi Zi(v),,
=
Vy (Voo, and (i) is from Lemma K.5 (ii) is from the definition of (vo).
Further, we consider Sa(vi-1jo/in) = v.) - q(vi-ap |ij = vv)ll,
lla(v v vi) 2(v2 |vjj =v))le,
(135)
(T(V") vi- (R() -o(v) vo (Re) -o(vove)))))
Σ
(Evee (R):- vo (R₂) -w(v.vv)))
-
((Re)- -F((", -0(===v())))))) (o) T(V v/-1, vi)( -
(136)
Eveen -(vo.vi) (2 (Ro) -v(Vo.v))
k
Eveen 7(V vi- vi) (1 7(v M[
T(vg.v( vv)
(137)
Vvrev (R)))llr: +E Evoen (Ra (.))
(8)
Pi-1
44
Me
1+ E
Eveen (R))
(138)
where (i) is from Lemma
K.6
Therefore, summarizing the above, we obtain
D
ve1)) Deu.aaviimnaaaalaaay.. v(jo)
(139)
2 pllavv = v Mejo) - a(vi = vipall max log q( = v/-1. Vejo)
q(vi = =Vi-1.
M
q(v2_ v vojo)
minlog
(140)
q(v q(v\_111 = vi-1 v
Vi-
Mr pt p--1)
1)(R, -1)(p,- + 1) [R + 1). ((yil1" vv, v1, + Re Ru ((V,, v", v.,t)+1
(R,-1
at ir llgg 1+
(141)
+ ((V, v², v2,t)
Define a((-) as:
n 1 Pe-1)
(R,_1 - 1)( +1
Al(v.) = 1
Pr. 1r
log 1 (R + 1) ((ViV'' ,v, v., + Ro-1/ Ri. -(Vi. v³,
v², v).
vo, v
+1
(142)
4/ pT 222)
We consider a upper bound on En A.. Let C. = I+((Vi," v.. we have
n
(R-1-1)(RR.)) 11)
A = C. Σ log 1+
(143)
(R + 1) S(NIIV" ,v",v,, + R4-1 R4 <(V,, v". (v, +1)
40

---

Published in Transactions on Machine Learning Research (06/2024)
A
(144)
From above, we have,
Dallavii-noMaallleei. + DKL (g(vi-1 Mai-----aall & Ai(v))
(145)
J.5 Proof of Lemma A.5
According to mcasure partition, we have split mcasure ((V.jo) into q(v: E Sa), E Sb) and q(v, E Se).
Therefore,
Eve Av(r) (v)() g(ve E S.) A.(v)) gvv. St) A.(v.) + g(v E S.) A.(v.)
(146)
Now, we consider the behavior of Ax(-) with respect to V; for each measure. For measure q(ve S.) and q(ve Se), since 5(V,vv', Ve,t) 2 Sim(V,, v*,t), we have
Ae(v.) S u put-//m - (T-1/H1) + Sim(V,, 11)
R2_1 -1 RE Sim() : ,v, + Sim(V), v*,t)
log(1 +
(147)
def
(148)
where Ar utt (pi - and B, R²-1 Here, use notation 3or instead of a single symbol is to clearly show how the order of privacy leakage varies with respect to in generation process. For measure q(v, E St), we have much smaller privacy leakage than (Vv, E Sa) and q(v, E S.). When the supp(Vo) supp();), Vilv" * 0, we have
A
A.(V,)
log
1
(149)
1 R" i=1
1
R - R
AA
B,
71 Ar B,
(150)
(1 (1+ R², [(1 + R
R
R R.
Therefore,
A, B.
Ev, Ev.la S q(v, E Sa)
gth +vvee E St)
+ g(V, E Sc).
(151)
n2? R?at!
sth
Now, based on the above partition, we further estimate the measure of g(v, E Sa), g(v. E Sa) and q(v, E S.).
Recall that N₁, (v") = Kv e Vi s.t. o(v, v*) < n.H.. We have the following:
q(v, E Sb) Sq(v;; (1)v, is diffused from vo E Vo s.t. a(v'vv)) m) $ (v*)
(152)
(153)
a(v, E S.) Sq vi (1)v, is diffused from vo E Vo s.t w(v., v²) 2 the and
(2)4'' Vo. ((v. v/) 2 t %/ 2) <q Vv(,,, is diffused from Vo E Vo s.t. @(vo, v*) 2 n + 1, vo) 2 7t 1/ + 22)
(154)
(155)
- Nn. min((n(11 7 1}
(156)
As for q(v, Sa), need further characterization. Let of be tunable positive constant and we have the following:
a(v, S.) Sq(V; diffused from vo Vo s.t. W(vo, v²) S m)
41

---

Published in Transactions on Machine Learning Research (06/2024)
V is diffused from Vo Vo s.t. a(vo. v²) E In + 1, (.).. v*) S m))
+V(v, is diffused from Vo Vo s.t. @(vo. v*) 2 (1 )m 1,0(ve. S mp)
(157)
Ny. (v')
(1+ 1n
AN (v')
n m- (14 " Na (v*)
max k=
(e (k- (itg (
(158)
1=
mergo together
M(1t)))) (v*)
Ma (v*)
max 1zb2(1+c)0
(n- (Ate yh yhu
(159)
8
(1) M(1tc))) (v*)
Ma1+0mm (v*)
heq
h-
he
max
9t
h 71-
(160)
s
1oc 2 Ii1
12 17c
n
(1) (v++)))(v"))
N(1+cmmle (v*) ((1 + (e)) ( <e< + (1 ( grim yovn 1c221
(161)
of
(i) is from (%) - en j and (it) from Corollary
K.1 where we need efty
< (i.c. k 2 3).
Narefime and e-Narepme [11 (()+)))))00 (5z n n 12s1 +
Now, we want further balance the two terms
(Ltette yi (1, yoi 1221
Natefine(")) (v*)
Nn (v') and [(] + G))) )( 1 +
L.e.
balancing
Naw (v") (Utalleyct (1, yo c,21 First, compare 8- N2n, (v*) and (2epz)
(1) If (v')
(2ej4, )r, we can find a smaller of make the bound Eq. [61 tight. Instead of working None (v-)
Natopm (v")
directly on ((1 + c))) (1t, c( S (-Naefmmmmy we consider a sufficient condition: found smallest of such that
N N(1+o)) (v*)
(2e) (1 <
(162)
N(1+otm (v*)
i.e.
D-Natopme (v")
log
No (v*) +1 log
Nt
2
(163)
log
P.
Select the smallest of that satisfies Eq.
63
Since (1 + mn E {0, ..., Let mo = [(1 + c')ml
(2) If Nam (v') e-N2m (v*) < (2ep4 )m )n, want find the smallest such that (1 (1r yo 8-Noa-e (v*).
Natoo) (v")
Similar, since (1+c)) )o S e, we also consider a sufficient condition: found smallest & such that
ct
Na (v*)
nh (ep jo
(164)
N(1 (v*)
i.e.
5 --N (v")
1 log
1)r
Netto in (v*)
c
(165)
log
1
19,
Select the smallest of that satisfies Eq. 165
42

---

Published in Transactions on Machine Learning Research (06/2024)
The above procedure for finding (1+ + of o) can be described in Algorithm ??. After finding the most suitable (1 + & me alv. E Sa) can be upper bounded by
2N (1 (v*) q(ve E S.) -
(166)
Na (v*)
Now, we examine the selection of T/. Our aim is to let g(v. E St) n.A. Ii__ Ri
dominated by 802
Consider the following sufficient condition:
N(1+o7o (v*)
Nu (v*)
n A. B, RG R4
(167)
8
8
i.e.
log (v")
Natofin (vn + log(AA Ce sx.))
1/ 2 max
(168)
2log Re
where C, = -1-
Note that the r.h.s is monotonically decreasing w.r.t Tt. However, since T/ E {0, 1,2, n.. n), we have to make sure the h.s is dominated by In fact, this constraint is naturally satisfied log( "v"n,(v") -0o when Mp- + n.
N(1+e))ee"") (v*)+ goes to
m6 2,,, Finally, we control the third term, N-" min((n(1 - )) -/ term (ate
to be dominated be the first
8P1 That is
Na (v*)
s (v*)
2
min - 17 )) 7 +2
(169)
i.e.
N(1+c) (v*) (v")
Ny, (v')
mmn (n(1 - 14. 13)
(170)
s
log (v')
Nattopin (v*) (v*)
T) 1/ + 2
(171)
log
min(n(1-at).a
Similarly, log( (v-), can goes to -o when T)t + and the above inequality naturally holds. Thus, we (x)++
combine the above results, we have when ne [n] satisfies:
e- s-Nm((v") log Natepmaly (V') + max
log a- Nn,)(("")
Nattoim, (v-J + log(Ar CC. sWx)
(v-)
M 2 log n(1 x(1-at)
0 -
(172)
21og Rs
Summarizing the above results, we obtain that
n Ev o) [v(()) Sq(v, E S.) su. + qqv, E Sb) n. Br
+ g(V, E S.) n
(173)
R2, Rin!
8
better bound estimate the third term is NN (v') P(W((vi, vo) 7t oof + 2) and
Insteed of using Eq. 156
Nate:7
(v)) (v")
trade-off with first. term, we get the smallest vp. '/f + such that P(w(ve, vo) 2 1/ %/ 2)
where
N (V*)
P(D(Ve, vo) 2 % + Emmm 72 (1) (at)
43

---

Published in Transactions on Machine Learning Research (06/2024)
4e (v-)
< min
.1
1
n
(174)
Summarizing the above results, we calculate the privacy bound of discrete diffusion model by following Algorithm ??.
J.6
Proof of Lemma A.6
Proof. To begin with,
E -y [DKL (Vvijo vi) q(vaj vi) vo)
(( (D
Van = v-)lla(v vv))l
(175)
~ (
Vejo va))
(176)
((Vel = vi) q(V.jo = ve)
Now consider o(v (Vv))vvv)
q(Vijo = vi) [(V111 = vt) 8 s (1 s(V,v'',
1
S
8 vwen
(177)
where Ω = (vil((), v", vv, > s}. Therefore,
o)) (al..((vv By
= v.) = vv)))
(178)
1 & q(vi=11 = 12-11 vz)
( = v vi-1lVe11 = vi)
((vijo = v.) log q( v.- Vej0 = vz)
(179)
1 V=1=1
Exsen 7(V,, vi-1 v!) ( q(v ((vi-111 vi [vij vi)
-B
log
(180)
1+ 5(V,,", v".
(v vi- Vejo v..)
a(v (e
Now consider log q(v 2-10 110 VV v.))
g(v (vi-111 v vi)
( vi-1 Vel v.)a(vejo V.)
log
log q(v V/-1o V8.0 velg(vej1 V.)
(181)
q(v V 1 vv)
=log(1
(.)) ([+ <(V,, v", vos vo,,t)
(182)
TiViiN 1.11)
1 1+ Evenn
((
Evee, T(v'', Ny wy
= log (1+
(183)
R (1+ Evorn (V (R,
(1)))VV..)))=(vvoxx) ((V, v², vo,
r(v6.vt -1 max ?(v")v((i))))
(184)
r(vb/vE_,,x)) max, -(v",_[_,))) <(Vi, v*, Vr, 1) +1
1. When v v/=v vti we further compare vi.1. v/: (1) vi_ = v/, we have =(verri_11))))
v(v')v] 11. (2) If v/2,, # #v.
((vi.v(_.vv)) < R-
we get ,(val));,,)))
Hence,
Ey Ev, (ww( = =vollllv vv)]]
(185)
1 Emerr 7(VE. v() (R.) ())) -
q(v) Q( 1/1 vi_1/v.j vz)
log
(186)
1 1 <(V,, vi,
q( v v;)
44

---

Published in Transactions on Machine Learning Research (06/2024)
Eveen Evi- s/v T(V), vi-1, v/) (Re))lv v1)-
R
(187)
1+ C(Vi, v', (2,()
R2 R v2, v(.
Eveen (1 - -((: Vo, vz)) (R.) (.) R 1-1
-
(188)
1 (-V, vr, (2,()
R
Mt (TBi-1) (ReBe--1 1)
(189)
RG 8(1 +)
1
Mi 1 -11
1
(1
). P(vejo 22)
(190)
s(s
Hi
Re
2. When v³ # v similarly, (1) V/-11 v/, we have % 1.1) <(oivi will
M. 189 S Ri-1/Re. (2) If vf # v/ we have
7(y M.nl)) S Re-1- Therefore
(y--oo(yn)-oovvpp o))
(DKLla(vi -1ill = v.))
(191)
Eveen 7(V0. v/-1: (M)))((".))))--)--)) ((vovvi)))
ạ( Q(vi-1j1 1-111 vi-1/v [-]//Vj1 = vo)
log
(192)
1+ 1+111, v Ve.t)
q(v v Vaj0 Vo)
Evoen Σv,, =v; T(V vi- vf) (R.)olv vw)-avov))))))))
R RR -1
<vsnglviohmmn
(193)
C(V,,, vi, v.,()
Re-1/ L.L//RC(V,,, v=,v,,
1 Evern Ev (Vo: vi-1, (R)))(vv,, -())
R4-1-1
+-
(194)
1 1+ +(V(,, v", (),
Re-15(V1, v*, vv,
I Eveen (R.-1-1 (Re 1)T(v) v/. v()) (R.)olv ((("".))))((oo)"))
= -B.Ng(vio)MEER
(195)
(1 + S(V,, v*, Ve, 1".
(RR,1 -
B/_ (Re - 1))
14.
(196)
Re-18(1 +)
1
(1-
(1
Mi Mi-1
(1 RA-1
1
)+ +
Mi p1-1
(1
Rs
P((eioo E 2
(197)
s(s 11)
Ai
pi
R
Compare two bounds Eq.
190 and Eq.
197 since we have
11 P
1
Me
P
Re
Me 11-
1
+
> (1
)(1
(198)
R
R
R
We derive the following bound:
(P ve))la(v?-110))
= vc))
(199)
<
1
(1 (1- Me 1
1) (1
1
)
Het pT-1 (1
R 1 )
.P(vjo E 22)
(200)
s(s 1)
n
R₁
J.7 Proof of Lemma D.1
Proof. Given adjacent datasets Vo, Vi and diffusion coefficients (ot (EET), we consider the probability transi- tions in the generation process.
Po(Ve-1yy Vony) =po(v2-11 Voig) po (122-1)1/V4))
(201)
45

---

Published in Transactions on Machine Learning Research (06/2024)
2
Σ
a(vi VoglVap)ee (Vo (ois)
(202)
1=1
Yo.5 =0
where j {0. 1} denote the dataset index.
For g(v%_1, vol wl), from Lemma K.2 WC obtain
17 -44-1 = Ci.
If v/ v== v/-11
When Vo = vi
If v V. Hi 11--1 =: Cz
a(vi-2lvi vo)
Hi
(203)
pt 14-1 U1.e
If v0 vi-11
When vO # v
If V + vo = vi-1
14 144-1 =: Oz.t
where we have Ci + C2. C1 + C2. and C₁, > Ci C2. < C2. Now, consider ((vej1) and q(V.jo). From the forward diffusion process, we have
(x, 2 + (s - 1) (7
((Vej [0] (7, ) + (8 1) (7tt)2
q(Vaj1 =
(204)
s
[0] [ pet 14.
<(vaj
(205)
[
and
2 (xtt) )² + (s 1). (1T) )2
[0] 2 (1 )2 + (5 1)
(xt))
q(V.jo
[0
(206)
8 1+1
8 8+1
1 (Vvajo 0
[0]] ptt iT.
q(vpp=
(207)
Further, we consider the prediction probability Po Mag). which is determined by the training of denoising networks. In the training procedure, we are optimizing the following objective function
minimize (q((()
II
(208)
f=1 Vela
From Lemma K.8 we obtain the optimal solution is when p (v (v = [(11)
Therefore, Po (v = I E =o ((v u(vi-1 Vogl ( )a [41s))
For (eslll we have the
following calculation: for dataset V1,
(s 1). (pt)) )²
0
(fg )²
q(vi) V/v
1) (pt)) )2 + (iT )2 ((v11 1/
0
(s 1) (xi )2 + (Mz )2
(s (s-1) 1). (FT)²
H
(I7. )2
a(vij = 0 V/
(s 1): (R,) ) + (M. )2 (Vvoj1 = 1/ve/1
(s 1) (H, )2 + (p. )²²
[]] )
s ((v2 = 1/ = [0] )
1
a(vij] = 0/ =
and for dataset Vo
[0]
1). (p:
[0]
2 (A, )2
q(vij = 0/vajo = 00 (s 1): (0t )2 + 2. (ū, )2
vVvij = 1 =
0
(s 1) (M. + 2- (0r )2
46

---

Published in Transactions on Machine Learning Research (06/2024)
(s - 1). (p
H]
2- (1,,)
q(Vijo = V/j
[(Vojo - 1 v =
1) (1t)) + 2 (1T))
1) (14 )2 + 2 (it
q(Vujo = 0 Vajo
8 1
VV = 1 1 [1]
00 2
)
1
x
For the convenience of further derivation, we introduce the notation 2j (12, = a(vo1s = =xilVo0= = for simplicity. Therefore,
22
0
Pv
Vels
(Ci. Øy (0 0) Ct. y (1))
0
0
Po(Vi-115
(C2,1 Øy (0 0) C22 qf (1)0,0))²
0
0
Po(Vi-115
=
(C2.. qf (0 0) C22 qf (1)0, (C1, (0(00, Cτ. (1)00))
0
0
PV
- Flaa
(C2, g (0)0, 0) C22 (1)0 (C1, (,00,, Cr. (1)0,))
0
PolVi-11
(C2, 9 (0 1) C2 y (1]1
1
Po(Vi-11
1
= (Gi, gj (0 1) Ct. (1),
1
PolVi-113
= (Ci, 9 (0 + C1. (1)1,, (0 (011 C2, (1(,
1
Do(Vi-114
1
= (G,, 9 (0), 1) + (1)1 ()) (011,1 Ca, (1(1,1
1
1
PV
= (Gi, 9 (1 0) Ct. (0)1 ()) (, (0),0)) C2, 9 (1)1,0)
0
1
(Gi, g (0 Ct. (111 Ca, (0),,))
0
411 Po(Vi-115
1
(a. g (0)1 0) Ct. (1)1, (11,,,)))( Cr. 4 (01,0))
0
411 11LV1111
1
(C2. (0 0) C2. (1l.../g111100000111.111 ((11, Ca. 4 (0]1,))
0
0
(Gi, Øf (1)1, 0) Ct. , (0)1 (0) 00 Ca, 4 (1 (1),0))
1
Po(Vi-115
(EA M
0
(Ci. yf (0)1 0) 1 (11110))((... C2. 4 (0]1,))
1
0
Po
SlAAl
(C2. (0 ( (1)) Ca, 4 (0),
1
0
Po(Vi-118
(Ci. g 0) Ct. (111, (1 CC, , (011,0)
H p (v.-11
H
With above the circumstances discussed above, we define Hr-1 = Ps (v--10
we
have
[
0
0
H--1 -P- (V = vyjo= =
[ Do Do (vejo =
1
+ Po Po (Vi-110 =
1
Vejo
0
)ps (Vejo =
[0]
[ Do (velo
[1]
[
[0]
[0]
+ +P = Vejo =
+ Pa. (v
Vejo
i
Ips (Velo =
[1]
1
47

---

Published in Transactions on Machine Learning Research (06/2024)
- -Vo(V
Maj
Do (Vaj
+ Po Po 1/1
Mejz
0
Po (vel
0
(9)
-Po(V,-1)
) + Po (v. 111
Wej
Po (v
(209)
H
1 [1]
(V
Vejo
(Vo(Vv
1
) po =
i Vejo
Mej H
+Po(Vi11
)pp(( 1100
po (v
+ +Vo(Vi-110
Vejo
(op
(Vejo
) pe (Vejz =
0 0
H Vejo
Mej [0] [00))
+Po(ViI1
(p Vt 111
Ps P (v--11
+Po(Vi-110
Vejo =
) (p
) pa (Vala =
H Vejo =
[ee = [ [)))
+Po(Vil1
(pp Vt 110
) ps (v
) Po (v = [1]
+ +Po(Ve-110
Vejo =
[1
) (p (V.jo =
H Vvjoo
Vep = [o [
+ +Po(Ven1
(v V
Po (v =
(210)
Since pol po(Veio (Vrio=
[1]
1 pa (Vel1
[] = Σ 11 (Po(Velo = =vi) - -Po(Ve = =v)) and max
ps (V:-10 =
[0)
Vejoo [ P = 1 |vejo = [|]]]] } Pa (v
H Vejo
Vejo- =
) Po
H Vejo
0
po Po 11-
[1]
we have
H Vejo H) po(
[1
H 2 pol (v
Vvjo =
0
Hr.
+ min po (v
|vajo v.) (o
H
[
Vap vo)
(211)
1
Vajo vve) po( H 1ap v.)] we have
For miny, pol Po(Ve-110-
Po(Vo-110= H] Vejo /00 ) pb( (v [] Vajs [0]
[0]
(212)
(ss 1)((2,1 C2,1) )2 )112(s 1)2 +3 1)( + (2t)(())?PP))) + 402, )*]
[(s 1) 2(7, [][[(s 11) + -1,, )
(213)
Pol Po(Vi-1j0- 1 Ivao- H) po 11] MMa Hp ((s 1)((r,t (o,t)(ttttttee (pT 1),C (1 + ( )
1
(214)
CG, [(s - 1) + 2(1, [][[(s 1) )2 (1t
(215)
Po(Vi-10= H Vejo = = HD) ps (v,-110== = 11
Vej1 = 0
(216)
48

---

Published in Transactions on Machine Learning Research (06/2024)
(s 1)((s² 2s 1)((C1, C2 Ct C2 + (C1, C2 Gi C2,1) + (3s + 1)( C2. Ct C2,)
52(s 1)2
(217)
From detailed calculation, can show that
1 min Po Po [] Vujo = vi) (v
|il1 - vv))
[1
(218)
(s 1)(c, - (2, (T, )3][2(s 1) 3(s 1)(C2,t C2.) ((Z,) +402, y
[(s - + - (14 2912
(219)
:=G
(220)
For / = 0, we have
MIJI = H
Pv(V (volvolo =
V1J0
- Po(Vo =
1
[
+ +Po(V111
(Volo
V1j0
(Voi1
V1 =
+ +Po(V1IL
(po (Volo
1
V110
0 - Po
(Voi1
11 =
0
+ PVo(1111
(pl Vooj
V1j0
- (Vol1
V11
(221)
1
1
[0] [0)
[0))
=Po(V111-
Po
+ Po (V111
(222)
sR
=: Gu
(223)
RR
H
H po (v 1 Vejoo ( we have
Let F, = (v =
Vejo =
F, 1 4(8 1)
(2 ) B- + (s 1)
(224)
(s +
1s,
where
A = (s 1) [(s 1)č1, - 1)Ci, 2C2,l.
(225)
B = (s + 1) C1. - (0ss-1)C,,+22,..l - 1) + 202a). 1)č1.
(226)
C (s (s+
1)C1, + 2C2,r]
(227)
Given that Hy 0, and by iteratively applying the inequality H G. F,Hr, arrive at the desired
conclusion.
J.8 Proof of Lemma D.2
Proof. Since q(vri (
g(vr) H) q(vri) [ <(vi)) =
0 [
From induction and
4'
symmetric properties, we obtain that for any 1, we have
[ a(v.j = !1 g(v.)
0
H
d(v.) o
2 g(v.j)
(228)
On the other hand,
[ o
1
M111 [ = ps pv (v. =
1 Vej = 0
Po(V,-111 Vaj
<ps (v.-111
49

---

Published in Transactions on Machine Learning Research (06/2024)
<Vo(V1-111= H Maja = H
(229)
Thus, using Chebyshev's incquality,
Po
Σ Po(
Mijs vvip =v))
(230)
1
Min1 b)
[
1 |ijs = [1] Drotviu H)
(Vo(Vol1
+ Pop (vol1
(231)
R²
H Vip v1))
< +
m
(Vi-
(232)
R7
s
V1
=0,(
(233)
where from proof of Lemma D.1
we have
min 1
C2.
R2
C2.
ČL.
C1. R2
2(
ČLa (s 1)
+
CL.r (2 1)
(s-
Cz.
}].
8 R +1
sR +
s R
s R2
8
8
(234)
K
Additional Lemmas and Proofs
Lemma K.1 (Monotonicity of KL Divergence). Let X2......... Xx..X.....,, be probability measures over random variables X1, ,2. where Px,:QA Qx, are the marginal measures of Pa.. and Xx, respectively. Then, by the monotonicity property of KL divergence, we have:
(Px,(Px (Px, Xx
(235)
Proof of Lemma K. The proof refer to Polyanskiy 2020
Lemma K.2 (Boundedness of Posterior Distribution). The posterior distribution in discrete diffusson process is given as q(v=-1/v,, vo) = -Cat(v=-iiv.0f o voQle1//oo.vv such that
Mr p min q(Ve-1lVe, vo) 14 P7-1 14t
max Vo.V
g(vi-1lV,,vo)
(236)
Vo.M--M.
Proof of Lemma K.
Since Q. =ad (1 k.) b
from definition, given L,j {1,2, ...,....,
a(v,-1/v V. = = =) layI + (1-a)) 11
a I + (1 a-11) 11 b.
$
(237)
C.)
1
oz)) T
[a (1-az)
l 114 14 .... M4 p1, 14 ...., pr
(238)
b.
11
ai- 1 + (1 - x.-1)
lt, [ M4
1
(239)
1. When == j, we have
11T
11T l1, + -a(-1)
[a + (1 an)
k br-
k
50

---

Published in Transactions on Machine Learning Research (06/2024)
P4 P Hi 14-1, Het 11-1 -P-1
(240)
1-1 terms
Besides,
117 adl + (1- 11--) [T.)
li. = 1t
(241)
k
Therefore, we have the explicit form for q(Vc-1lv = 1. = j)
|i
14-1
11 11-11
Pb 144
Pi 144
14 14
dve-ilv: = = =)
(242)
14
14
14g
14g
2. When jj we have
11
11
last + (1 ar)
h lt, 2 [Q-1 (1 - xx-1)
k 1s.
jug M 1--1 Hi 1i-1. Hi Pi vun p P ue 1.. Mr 17-11
(243)
j-1-1 terms
11
a + (1 - σre)
lis = b4
(244)
h
The explicit form of q(v:-1/v, vo = =] given as:
(v--1lv, vo = j) 1i 1
Hi 1T-1
1e Pi
(245)
The
Te.
14.
From above derivation, we can show that
max (VV.-I/Ve, vo) 1t pot Vo.Ve-
14 14
min q(Ve-1/Ve, vn)
(246)
P. Vo
Lemma K.3. Given positive bounded trivariate kernel K(x, z) such that K(I,,ū,)) E [cr, and the conditional probabilities (i62) and px(2)) satisfy
DRL (x S V2.
Define (=(2)) and (z(2))
(x(22) / K(x,, H, 22) p((122) = / K(x, 21)( ie [0,1].
(247)
we have
Eg [DKL (p) < E, [[a_(a[aak)](a[([)])]]) + & k 7
(248)
V
Proof of Lemma
K. From Pinsker's incquality, we have
J - - (d(=))/d < (
/ ie (0.1)
(249)
2
Since posilive kernel (, E [e1, o2), have
(0:(2|2) [x(211)] = [ (11,,,2))0 (c - & ez 2
51

---

Published in Transactions on Machine Learning Research (06/2024)
Thus, [1]((=]2) (xl s ook Now, for any given 2, we consider Ja po(x)2) log po(2))) Ja 2o (2|2) log s
p1(z(2)
po po(x)22) log po(x|2) (pn(arl)) (0(=l=)) p1((l==) + / [o(x)))(log po(x]2)
pı (z]zz) - / (0(x)))) log (0(x]2)
@ (x|22
21 (x(lz)
+ log
p1(0(2)
[u(x|z)
pr (x(())
a / [[0(=t))-
- xx(11=]++ + -00e=))))()))] -/
ci / [e((0l2) (x(22)
2/ - / -o(ola)-00(<=))]) c0(x|=)]+ (0(()))) (1)))))))())))))
61
k
7
9
We take expectation on both sides and we obtain the result.
Lemma K.4. If H. be = Eg as we have
1 211b - alle, (max c; - minc.) (b, - -ale S
Proof of Lemma K.4 First, WTOG we can assume by - 01 2 b2 02 2 ... bb a, 2 2 6 - a,41 2
by On- Since Σ, b; E, ai, we have Σj=(bb - aa)) E. (b; - a,) 211bb allı, Further, we
have
n
E0,; (b: az)) Ci Σ (bg - .
Σ
(by - (bj= cs
(250)
5=1
s
Σ (b, - a.): +
Σ (-(b, a,)) (-ca)
(251)
1=1
$ max c; 2 11b - all; min c;) _ 1 - all:
(252)
1
2 6b a all,, (max e; minc.)
(253)
Lemma K.5. For x, 2 0,
(a+ + 1)y + (ar + y +) + x +x+++1)
a a+1
I (a2 + 1)x + ay + az +
(254)
Proof of Lemma K.5 We reformulate the above inequality into a polynomial division problem. Define a multivariate linear function f(z y, 2) Mix M2y + M32 + M, such that
[(a + 1)y + 2] v() < (ax + y + (ay + x +
(255)
We expand the terms both sides, have
R.H.S- L.H.S
(256)
=Ia² - Mi + 1) (a M2(a + 1)]8² + ((a + -
1)-1) - MM(a + 1))yz
+ ar² - zy + + M1)a2 + (1 M2)²² + ax [] M,(a + 1)1y + (1 - M4)x
(257)
52

---

Published in Transactions on Machine Learning Research (06/2024)
Let M1 a=l
a²+1 M2 M2- atI. M3 a and M4 at. we further have
2a
1
R.H.S- L.H.S
a a y2 + ax² 2 +
xy +
2²
oz + 2
0
(258)
a a+1
a+1
1
a a+1
Thus, we prove the incquality.
Lemma K.6. We upper bound the total variation of conditional probability gap as follows:
If vi- v we have
Pi. (1
Rs p. R
11(vi=11olvvj0 v.) - -ivvi-uulvap v.)ll, S 1 ((1,,
(259)
If v3 A vii we have
Pi-1 R 1)
Pi Re
11a (la(v: = v1) - =ivi--nplve = v.)ll,,
nre
(260)
+ C(V, v", ve,(!)
Proof of Lemma
K.6 When v₂ = vtd we have
11a Vejo = vi) q(vi-1p//Va Val1 ve)lls
(261)
Σ
(glv) (alvi- = vz) -(vv/-11 -a11= = v.))+
(262)
Ever, vi (1 - s(v/.v) (.vi)
=(v"',r ) (R.) (ov) (())))(v".))))_(0.. -((vo..)))
Σ
(263)
(EvoEv,
+ Eveer, (Rt (o))))(())))
vi 1=
Emen, (1- - 7(v
=(v .xs) (v))
vi) (())
(v" vtl vi)) (Ever (Re (t))) -(vo.)))) )(
(264)
Emer, (R,) S0 (vo.vv))
Mt: P_ (1 (1- Ri-1 EvGER (Be) (R)
14
(265)
Eveer (Ro) (v))) vv)) E (R.
Sut pi-1. Re
1
(266)
14 Re-1
1 +(V,, v*, tt)
where (i) is from that 7(Vo. vi-1o (t)/ < 1 if and only if v = vni
2. When v # v*i, to simplify the notation, we abbreviate the terms as:
T(V vi) (1 - -(v6.vE_..V) -(v"iM-- ) (v))
k Σ
Σ Σ1Σ V-1
Σ
<(V1, v", v., 01 + <(V,, v", vt,ve, ())
Vo
v
1
VoEN
7(V vf v( v() (1- 7(v 1.l (Re) Rv xe) ((v..)))
Σ
Σ
5(V,, v", v., + <(V, v", vt,
VoEVi
vV=
voEV
T(V vi (1
7(v6.v/_
) (Ra (V ((v.)))
E1
Σ
C(V,, V1, v,, + +(V1, v", v,,))
VoEVi
vi (
VoEV
53

---

Published in Transactions on Machine Learning Research (06/2024)
k 7(V v/- (1 7(v"1, -(v-",;-,..1)))
(oo(v",)))-200 (R))) -()oo))).)))
Σ
Σ
5(1, VV,,v,Vi, v), +
v", ((2,,V',e.1
vi 1 Vo=v
vi
vovi
We have
110(v/-100/v100 = vo) - -vvii - = v.)l==
Σ
(267)
VoEVi
Σ
Σ
|+
Σ
Σ
+
Σ
+
Σ
(268)
v Vi-
VoEV
"-nzvii vi votv
V vi
Vo=v
v
VOEN
Σ
Σ
Σ
Σ
E-
Σ
Σ
Σ
Σ
(269)
Fy VoEN
v/
VorV
Vi
VI VoEN
E
Σ
+
Σ
Σ
Σ
VL VoE
vi
Vozy
[-]
VO=V
- (2
Σ
Σ
+
E)
Σ
(270)
VD=V
VoEV
Σ
Σ
-2 Σ
Σ
Σ
(271)
/i VoEVi
Vi
Vi_ vy Vo=V
Vi_ VoEV
2
Σ
Σ
2 Σ
Σ
(272)
YoEN
VoEVi
V/,,vv vo=v;
Therefore, from above we have
2 alavv /lolvi-jolVvoo- = vv)) - (ivi=-n1/Vay = v.)lls
1
(273)
v2,, vi) Evern, (1 v(v()
r(v"),,..);) - (R:) (v)-v))
S-r s-r(v",
(5(V, VV, t), + <(v, v(,t))
EvoEtiNozvi (1- 7(v-ivi-_
-(vi
(R))(vv -.)
Σ Viri,vi v.)
(274)
('(V),V',v. Ve, (1 + v(V,,, vi,
vi_, [v
( (R)))(M
Ri-1 11-1
1) (5(V), V Vo, f)) + ((V,, v*, v*, t))
(275)
14
Ri
(R.) ( ((oo))))
He Pr-
(Re- 1) (5(V), V", (1, + 5(1, v", v))
(276)
Pr
(
11
Rr-1 - 1). 1 ((VI.v
c
(277)
Pe
Ri
is from the fact that
P1-1
Rr-1 - 1)
14 14-11 (Re - 1)
(278)
Ri
R
1
1 + (k - 1)a;
1 - ae 1 >1 1
1)
(279)
Rs
R₂ -
1 (k: - 1)b,, 0,_1 1 04.
54

---

Published in Transactions on Machine Learning Research (06/2024)
Lemma K.7. Given [n], when ep I 5.4 we have the following results
ch
"
ch and
1j 1 argmax
q n-
17 q h-n is monotonically decreasing,
(280)
hike (.+
eqh h-n
eqh h
h-
2 argmax
and
is monolonically decreasing.
(281)
h-
h 1chef2n..2gg 2nt,,,t
In the second equation, we assume
1
Proof of Lemma K. We first show 17 + argmax/aee/tt.....
ch
gh h n:=;;
Let x + h, and f(x) = ((1 + }))= Easy to show that f(x) =
ch
n Now consider f(x)/((x + 1):
f(x)
((1 + 7f
+ )
(282)
J(x + 1) ((1 + z+1 me)
(1 + 1)
Now compare (1 + x) and (17 + x + 1)q", since
+ x +
'd
1 > 79
(283)
17 7+1
Thus, when eg S 3. fxx is monotonically decrcasing. Therefore,
ch
f(x) -1 (12........
argmax
argmax lch.n)t.....))
gk-n
(284)
h-n oghi h-
We now show 2n = argmax 22
Let = 77 h n S n 77, and f(x) (eq(1 )))² Consider the monotonicity of f(x).
f'(x) = (eg(1 + ") log(eq(1 + ") x +
"
(285)
Further consider log(eq(1+ + )))
Let { N/ < 2 1, s & 1, (EE) = log + {)) I7c 2 x+ÿ
E
5(() (1 + E)2 < 0
(286)
Hence, is monotonically decreasing. When 1. (1) = log(2) + log(eq) - < O. Thus, f((x) < 0 for x E {n. 1 + 1,..., n - 17) f(z) therefore monotonically decreasing.
egh h-n
7 argmax
f(x) <> 2n
argmax (2n.2
(287)
h
Corollary K.1. Given n E [n), when op S. Define
( ch
h-n egh h-m
f(h) min min
(288)
-1-11 1)
We have
(eh
When h E (n+ 1,7 + +2, 2,.,, min 11 1,
q"
17
f(h) =
(289)
and h E (2n, (2m,..,,n), [.. = ( egh
h-n
n When 9 7/
h 1h-1
55

---

Published in Transactions on Machine Learning Research (06/2024)
Lemma K.8 (Optimality of vo(v)lve)). Let q(-) and Pe denote the probability measure in the forward diffusion and backward denoising process respectively. In the training procedure, we are actually solving the following optimization problem:
minimize DKL g(vo))]
II
Σ po (volve) ((vi))
(290)
1=1
and the optimal solution is obtained when Pa (v/lv,) ((volv)).
Proof of Lemma K.8 Reformulate the KL divergence as follows:
minimize DKL ((vo))l II Σ
Po Po(vólve) ((vi))
(291)
2=1 W
maximize
[a(vo)log log II
(vóvvv))) g(ve)
(292)
Vo
x=1
Let pi(v)) = Er.rolvlvv) ((v.). The above objective is Evo ((vo) log Further define (((v)) =
En, a(vôlv.) ((ve).
Σ ((vo) log
II
II ((vólv))-9910 - En ((vo) log II I Po (v
(293)
im
Σ ((vo) log II (v()v Σ v(vo) log II (v()
(294)
log (v(v)) 1=1 (v((V))
Cv(vb vo...., vo)
(295)
(ai (vo.la(v 0
(296)
Therefore, the equality hold when Ps (villv))) = a(vólve).
L Specific Discussion on T(vi, v vi=1; v²)
Recall that
(VV v v/) ((+t) sav (+, fogtr [( ب (ftT1) ( 1
(297)
(nt I Auizzi (,,, fujzna
There are in total five possible conditions:
at P4
If vi-i== = vt and va = vi T(Vi, vi-1. v/)
If T = vf and v * v T(v/- v v/ v\) Proz
14 M, ai p.
If V * v and v v T(V vi-1. v/)
If v # vs and va v 7(1/. v v/)
Mr Mt
P.
If f v and v # v and vo + v T(Vi, vi-1, v/) =
A.
56

---

Published in Transactions on Machine Learning Research (06/2024)
Since in the derivation, encounter the ratio T(Vo, vi-1; (v)/ vi-1, vi). Therefore, we discuss the ratio a(v yo= / =o10= o//
in detail here. Define s((vi, và, vi-1, vf) = F(y"l Mi- slv - = 2lv) 110 yo following, we will denote it simply as R.
In the
When vi vti
-I[v/- v and v vy: K
-If v and vo # vi: hi- 1tri11
Re/Ra-1 <1
Pi
-Ifv # v and v = V A =
-IT # v and v # vs and va= = v/-11 K
P. P.
R2 Ru > 1
-ff + v and v + vi and v + v
-= Rg
R,
When v/ + v"i
- vf v and v v/,
Mt 1h4 14!
R >
-Ifvi-1 v and v 1 vt: x
[f # v and vi-1 = vni)
and v = vi, k
87 "T
1/) <1
If (V - v and v * v*) and va v 4r =1/Pe= <1
2.
If (vi-1 # v and v = vn) and va # vi and va = v/-11 K k=
If (vi_1 # v and v * vn)) and v v and vi v/-11 K
R > 1
Pr11
If (vi_1 * v and v = ) and v * v and vi * v/-11 k=
Pr
1/R1-1 <1
P
If + v and v + )i) and v
vi and vs + v v1-1 k=1
Further, we define Riv*i, vo. vi vf) ((biii_
[ 1o Jo -yg
When vs = vi
-If = v and v/= = v/; R ==
- -Irv/_I v and v # v ă
Pr- =11=10 =1/1 <1
IIf v and va v/. ń =
-If # v and v v
po RR-1 >
- II + v and v + v and v + V1-1, R=1
When vi # ""
PL. P.
-Tr v and v = v/. π ==
R
-ff v and v/A # v/ R = 1
If (V/_) # v and v vt)
and vaJ vi
1/R,-/ R <
If (vi_1 # 3a and v # ) and va = vi, h =
TI (v/_1 va and v = v* and va # vs and v/ v
(-17 R =1
57

---

Published in Transactions on Machine Learning Research (06/2024)
If (vi-1 # v and v # vnt) and va # vi and v/ = -v--1; R=
R > -
1/-1
- II (v/-1 # 1a and vi = vnt) and vg # ! and vs + v/-1, k.
Pr-1
= <1
P[-1
If (vi_) # 1 and v # vni) and vo 3. and v/J * vi R=
58


Reviews:
[{"review_id": "rachpzZilF", "reviewer": "Reviewer_eTtK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n1. The authors have provided very interesting theoretical results based on the pDP concept.\n\n2. The authors have empirically verified their theoretical findings on both synthetic and real-world datasets\n\n3. The paper is well-written and presented.\n\n**Weaknesses**\n\n1. From the paper: \"We evaluate the data-dependent part by removing the most sensitive data points (according to our data-dependent privacy parameters) from the dataset to train a DDM, and then evaluating the ML models trained based on the synthetic dataset generated by the DDM. Interestingly, we observe that the ML models obtained after a part of data removal can even outperform others without such data removal. We attribute this to the fact that the removed data points are likely outliers which may be actually not good for ML models to learn from. This illustrates another potentially valuable usage of our data-dependent analysis.\" : I believe simply removing data points identified as outliers may not suffice. Intriguingly, the authors in [1] have introduced a phenomenon they term the 'Onion Effect' This effect emerges when, upon the deletion of an initial group of outliers, a new set of outliers becomes apparent. Additionally, your analysis implies—and I concur—that increasing the training dataset size tends to mitigate risk. Therefore, removing data points and retraining the DDM on this now reduced dataset could potentially intensify the issue of privacy leakage.\n\n[1] Carlini, N., Jagielski, M., Zhang, C., Papernot, N., Terzis, A., & Tramer, F. (2022). The privacy onion effect: Memorization is relative. Advances in Neural Information Processing Systems, 35, 13263-13276.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces the first theoretical exploration into how discrete diffusion models (DDMs), used for creating discrete datasets, preserve privacy. Specifically, it uses the concept of per-instance differential privacy (pDP) to assess potential privacy risks for individual data points within a training dataset. This involves understanding how the privacy loss of each data point is influenced by the overall distribution of the dataset. It finds that privacy risks increase as the model transitions from generating pure noise to producing synthetic data. Additionally, it notes that a quicker decrease in diffusion coefficients can strengthen privacy protections. The authors validate their theoretical insights by applying them to both synthetic and real-world datasets, thereby confirming their practical applicability.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Could you please assess whether the ''Onion Effect' occurs in your case? For evaluation, I believe that employing membership inference attacks, as you did in Section 4.2.2, could be an effective approach.", "broader_impact_concerns": "Nothing to report.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "zSHIvwpmwZ", "reviewer": "Reviewer_hAZk", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In general, I think this is a good paper.\n\nStrength: \n\n1. Diffusion model is a very important model in computer vision and many other tasks. Any privacy guarantee on those models has great potential to help the applications of diffusion models.\n\n2. The theoretical analysis looks promising to me, which analyzes the per-instance DP property of DDM\n\n3. The presentation of the main contribution is great! I like Figure 2 and Figure 3, great job!\n\nWeakness:\n\n1. The notations need to be defined before use, especially the abstract and introduction\n\n2. Minor things on presentation (see the requested changes below)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the per-instance DP (pDP) property of discrete denoising diffusion models.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. I suggest adding a highlight to discuss why Theorem 1 is not true for continuous diffusion models. Even though $k$ appeared in equation (8) of Theorem 1, it's not quite clear (at least to me) what if $k\\to\\infty$, which corresponds to the continuous diffusion model (more general and has more application scenarios).\n\n2. In the abstract, $s$ needs to be defined before using. At the bottom of page 2, $m$ needs to be defined before using.\n\n3. I suggest moving the algorithm to remove sensitive data to the main text. I think the algorithm is very important because it can increase both privacy and accuracy if removing ~2% according to the experiment. I'm also curious about the time complexity of the algorithm. Can the authors provide any analysis?", "broader_impact_concerns": "Nothing within my scope.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "dWkv5IPjv5", "reviewer": "Reviewer_UWmy", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1.\tThe paper focuses on a timely question: the relationship between privacy and diffusion model. \n2.\tThe experiments are carefully designed and they provide strong evidence that the theoretical results well align with empirical findings.\n3.\tThe paper's emphasis on the nuanced relationship between data size, diffusion coefficients, and privacy leakage bounds contributes to a better understanding of the nature of this problem.\n\nWeakness:\nI am not an expert in diffusion model but it seems to me that the theoretical results within the context of p-DP are equally important as that of within the context of p-DP. It might be of better readers’ interest to reveal the relationship between privacy and diffusion model under the original notion of DP, which is more widely acknowledged.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the inherent privacy guarantee of discrete diffusion model (DDM), providing an upper bound on the privacy parameter $\\delta$, namely, failure property, under the definition of per-instance differential privacy (p-DP). Through empirical verification on synthetic and real-world datasets, the research underscores the role of diffusion models in mitigating privacy risks associated with data sharing. It leads to the conclusion that privacy-preserving techniques should be applied along with the training of diffusion model.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "According the discussion above, the paper might benefit from repositioning Theorem E.1 and relevant discussion to the main body of paper.", "broader_impact_concerns": "I do not think it is necessary to add more discussion on ethical or societal impacts.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: There are couple of minor things I think need to be fixed before the final version:
- Fig 1 "Diffuion"
- "evaluate how the potential privacy leakage if one uses DDMs to generate synthetic datasets.", is the "how" there a typo, or is something else missing from the sentence?
- Is the $\overline{\lambda}$ used in definition of $d^{(t)}(v)$ defined somewhere?
- Maybe you could add the linear lines for Figures 5 LEFT and MIDDLE, to illustrate how close the bounds are to the $1/s$ and $1/s^2$.
Decision: Accept (poster)