Statistical Theory of Differentially Private Marginal-based Data Synthesis Algorithms
Authors: Ximing Li
Chendi Wang
Guang Cheng
Venue: ICLR 2023 poster (2023)
Keywords: Synthetic data
differential privacy
marginal-based method
Bayesian network
learning theory

Abstract:  Marginal-based methods achieve promising performance in the synthetic data competition hosted by the National Institute of Standards and Technology (NIST).
 To deal with high-dimensional data, the distribution of synthetic data is represented by a probabilistic graphical model (e.g., a Bayesian network), while the raw data distribution is approximated by a collection of low-dimensional marginals.
 Differential privacy (DP) is guaranteed by introducing random noise to each low-dimensional marginal distribution.
 Despite its promising performance in practice, the statistical properties of marginal-based methods are rarely studied in the literature.
 In this paper, we study DP data synthesis algorithms based on Bayesian networks (BN) from a statistical perspective. We establish a rigorous accuracy guarantee for BN-based algorithms, where the errors are measured by the total variation (TV) distance or the $L^2$ distance. 
 Related to downstream machine learning tasks, an upper bound for the utility error of the DP synthetic data is also derived. To complete the picture, we establish a lower bound for TV accuracy that holds for every $\epsilon$-DP synthetic data generator.

STATISTICAL THEORY OF DIFFERENTIALLY PRIVATE MARGINAL-BASED DATA SYNTHESIS ALGORIHTMM
Ximing Li Tsinghua University
Chendi Wang
Shenzhen Research Institute of Big Data & University of Pennsylvania Philadelphia, PA 19104, USA {chendi) upenn. edu
Beijing, 100084, P. R. China (1i-xml 9) @ma i 1s. t.singhua. edu. cn
Guang Cheng
Department of Statistics University of California, Los Angeles Los Angeles, CA 90095, USA (guangchengj@ucls..ee
ABSTRACT
Marginal-basel methods achieve promising performance in the synthetic data competition hosted by the National Institute of Standards and Technology (NIST). To deal with high- dimenssiaa data, the distribution of synthetic data is repre- sented by probabilistic graphical model (e.g.. a Bayesian network), while the raw data distribution is approximated by collection of low-dimensional marginals. Differential privacy (DP) is guaranteed by introducing random noise to each low- dimensional marginal distribution. Despite its promising performance in practice, the statistical properties of marginal-based methods are rarely studied in the lit- erature. this paper, we study DP data synthesis algorithms based on Bayesian networks (BN) from a statistical perspective. We establish rigorous accuracy guarantee for BN-based algorithms, where the errors are measured by the total variation (TV) distance or the L,2 distance. Related to downstream machine learn- ing tasks, an upper bound for the utility error of the DP synthetic data is also derived. To complete the picture, we establish lower bound for TV accuracy that holds for every eDDP synthetic data generator.
INTRODUCTION
In recent years, the problem of privacy-preservivn data analysis has become increasingly important and differential privacy (Dwork et al.] (2066) appears as the foundation of data privacy. Differential privacy (DP) techniques are widely adopted by industrial companies and the U.S. Census Bureau
(Johnson et al.) 2017 Erlingsson et al. 2014 Nguyěn et al. 2016: The U.S. Census Bureau 2020 Abowd 2018).
One important method to protect data privacy is differentially private data synthesis (DPDS). In the setting of DPDS, synthetic dataset is generated by some DP data synthesis algorithms from a real dataset. Then, one can release the synthetic dataset and the real dataset will be protected. Recently, National Institutes of Standards and Technology (NIST) organized the differential privacy synthetic data competition (NIST) 2018 2019 2020-2021). In the NIST competition, the state-of- the-art algorithms are marginal-basse
(McKenna al. (02T). where the synthetic dataset drawn from noisy marginal distribution estimated by the real dataset. To deal with high-dimensional data, the distribution is usually modeled by the probabilistic graphical model (PGM) such as the
Bayesian networks Markov random fields (Jordan 1999 Wainwright al. 2008 Zhang al.
2017 Mckenna et al. 2019 Cai et al. 2021).
Despite its empirical success in releasing high-dimg dithnniieniii data, far know, the theoretical guarantee of marginal haase based DPDS approaches is rarely studied in literature. In this paper, we focus
DPDS algorithm based on the Bayesian networks (BN) known as the Priv PrivBayes (Zhang al.,

---

Published as a conference paper at ICLR 2023
2017) that is widely used in synthesizing sparse data (sparsity measured by the degree of BN that will be defined later). A BN is a directed acyclic graph where each vertex is a low-dimensional marginal distribution and each edge is the conditional distribution between two vertices. It approx- imates the high-dimensional distribution of the raw data with a set of well-chosen low-dimensional distributions. Random noise is added to each low-dimensional marginal to achieve differential pri- vacy. We aim to analyze the narginal-basee approach from a statistical perspective and measure the accuracy of PrivBayes under different statistical distances including the total variation distance or the L distance.
Another metric of synthetic data we are interested in is the utility metric related to downstream machine learning tasks. Empirical evaluation of synthetic data in downstream machine learning tasks is widely studied in literature. Existing utility metrics include Train on Synthetic data and Test on Real data (TSTR, (Esteban et al. (017 and Synthetic Ranking Agreement (SRA, (Jordon et al.) 2018). To our best knowledge, most of these utility evaluation methods are empirical without theoretical guarantee. Establishing the statistical learning theory of synthetic data is another concern of this paper. Precisely, we focus on the statistical theory of PrivBayes based on the TSTR error.
Our contributions. Our contributions are three-fold. First, we theoretically analyze the marginal- based synthetic data generation and derive an upper bound on the TV distance and L distance between real data and synthetic data. The upper bounds show that the Bayesian network structure mitigates the "curse of dimensionality". An upper bound for the sparsity of real data is also derived from the accuracy bounds. Second, we evaluate the utility of the synthetic data from downstream supervised learning tasks theoretically. Precisely, we bound the TSTR error between the predictors trained on real data and synthetic data. Third, we establish lower bound for the TV distance between the synthetic data distribution and the real data distribution.
1.1 RELATED WORKS AND COMPARISONS
Broadly speaking, our work is related to a vast body of work in differential privacy (Dinur & Nis-
sim 2003 Dwork & Nissim 2004 Blum et al. 20055
2005k Dwork al.
2007 Nissim et al. 2007: Barak
ct al. 2007; McSherry & Talwar 2007: Machanavajjhala et al.) 2008 Dwork et al. 2015). For
example, McSherry Talwar (2007) proposed the exponential mechanism that is widely used in
practice. Machanavajjhala et al. (2008) discussed privacy for histogram data by sampling from the perturbed cell probabilities. However, these methods are not efficient for releasing high dimeesinnn tabular data, since the domain size grows exponentially in the dimension (which is known as "the approach (Zhang et al. 2017: Qardaji al. 2014 Zhang et al. 2021). Zhang al. (017)) approximated the raw dataset by a sparse Bayesian network and then added noise to each vertex in the graph. [Zhang let al. (2221) selected a collection of 2-way marginals and a gradually updating method was applied to release synthetic data. Although most of them provide rigorous privacy guarantees, theoretical analysis on accuracy is rare. Wasserman & Zhou (010)) established a statistical framework of DP and derived the accuracy of distribution estimated by noisy histograms. Our setting is different from theirs. Precisely, we analyze how noise addition and post-processing affect the conditional distri- bution (Lemma 6.2p. Moreover, our proof handles the non-trivial interaction between the Bayesian network and noise addition.
curse of dimensionality"). The ofate-of-art method for this problem is the marginal-bast
Our lower bound (Theorem 5.1 is related to existing results of the worst case lower bounds under the DP constraint in literature (Hardt & Talwar, 2010) Ullman 2013 Bassily et al. 2014 Steinke & Ullman 2017). Hardt & Talwar (2010) established lower bounds for the accuracy of answering linear queries with privacy budget e. U1lman (2013) derived the worst-case result that in general, is NP-hard to release private synthetic data which accurately preserves all two-dimensional marginals.
Bassily et al. (2014) built on their result and further developed lower bounds for the excess risk for every (c, 8) DP algorithm. Our result is novel since consider private synthetic data and the corresponding TV accuracy. Existing results for linear quires are not directly applicable to TV accuracy since they heavily rely on the linear structure.
2

---

Published as a conference paper at ICLR 2023
2 DIFFERENTIAL PRIVACY
Differential privacy requires that any particular element in the raw dataset has limited influence on the output (Dwork et al., 2006). The definition is formalized follows. Here the data domain is denoted as S.
Definition 2.1 ((c, di-fffeerlttial privacy). Let A: 92" - R be randomized algorithm that takes a dataset of size n as input, where the oulput space R is a probability spuce. For every e, 2 A satisfies (e, -ddiffferlllial privacy for every two udjacent dalasets D1 and D2, we have
P[A(D;) S] S exp(e)P(A(D2) E S)
for all measurable S R.
Here Dj and D2 datasets of size n. We say that they adjacent if they differ only single element, denoted as D1 = D2-
For d = 0, we abbreviate the definition as e-differential privacy (c-DP). A widely used meta- mechanism to ensure c-DP is the Laplace mechanism. The Laplace mechanism privatizes function f on the dataset D by adding ii.d. Laplace noises (denoted as ~ Lap(A) to each output value of
f(D). Here the probability density function of r) is given by Pin x] 2A exp(=x" Dwork & Nissim 20044 show that it ensures c-DP when X 2 A,/c, where A is the L' sensitivity of f:
A
max (D,,D)):,, [I ((D2)
3
MARGINAL-BASED DATA SYNTHESIS ALGORITTMS
In this section, we introduce DP marginal- based methods. For simplicity, consider Boolean data where . = {0, 1j4 and [|] = 24. It's obvious that our theory can be generalized to any categorical dataset with finite domain size.
3.1 DIFFERENTIALLY PRIVATE ESTIMATE OF LOW-DIMENSIONAL MARGINAL DISTRIBUTIONS
Given dataset D = (a. Ji C CΩ" drawn independently from distribution, the probability mass function is estimated by
pD(x)
1 x].
for all Ω.
n
Noise addition and post processing. We then sanitize (z) by the Laplace mechanism. Note that the sensitivity of (D( is 1/n. Then, we define PD = PD + Lap(1/(nc)) and eo is c-DP. Adding noise leads to inconsistency. To be specific, some estimated probabilities may be negative and the overall summation may not be The following two kinds of post processing methods address the inconsistency are widely adopted in marginal-bast methods (cf., (Mekenna et al. 2019 Zhang al. 2017)).
Normalization. We convert all the negative probabilities to zeros, and then normalize all the proba- bilities by scalar such that their summation is 1.
L Li-projection. We project the inconsistent distribution onto the probability simplex using the L metric. Specifically, for an inconsistent distribution (a1, ... am), the output is
(b,, .b,)
arg min
Σ (a b.)
2,20, Σ he 1=1
3.2 MARGINAL SELECTION AND BAYESIAN NETWORKS
is well-known that marginal- based methods have the curse of dimensionality. One way to mitigate the curse of dimensionality is adopting Bayesian networks (Zhang al. (017).
3

---

Published as a conference paper at ICLR 2023
Marginal selection. We first disassemble the raw dataset into a group of lower dimensional marginal datasets. Precisely, PrivBayes (Zhang et al. 2017) uses a sparse Bayesian network {z1. ... _2a to approximate the raw data. Each node 2; corresponds to an attribute, and each edge from 2j to x; represents [[ my.] which is the probability of zy causing Zi,- We denote πΙ, == {j zjj + xi which is the collection of all the attributes that affect x; ZZhan et al. (2017) also make the following assumptions on the network structure. Here k is pre-fixed parameter that is much smaller than d. Assumption 3.1 (Sparsity). The degree of the Bayesian network is no more than k. Precisely, for any i, the size of [I is more than k.
The second assumption ensures that the graph cannot contain loops, which aids sampling from the graph.
Assumption 3.2. For any i, we have II, ( I
For example, the Bayesian network in Figure 1 satisfies Assumption 3.1 for k 2 and Assumption The joint distribution (5 | P4 3, 2)P(3 | (2 1).
3.2
2
Figure 1: A Bayesian network over attributes of degree
DP Bayesian networks. In Bayesian network, each low-dimensional marginal distribution P(r;, II,) is estimated by the marginal function defined by [ For privacy consideration, we add Laplace noise Lap(d/ne) the marginal P(22,,I, and obtain the DP distribution P(z;, II,] by ing post processing to the noisy marginal. Then the overall privacy budget can be calculated by the composition property of DP (Dwork 2008 Zhang et al., 2017) and is
Generating synthetic data. The loop-free Bayesian network provides an efficient sampling ap- proach. Precisely, we draw x, from P[r, 11,] in an increasing order of i. Recall that Assumption 3.2 ensures that xj & II, for any j>i. Therefore, by the time x; is to be sampled, all nodes II; must have been sampled. This verifies that the sampling approach is practical. Moreover, sampling e, only needs the marginal P P[,r,, II:], instead of the full distribution. By Assumption 3.1 it is marginal with size less than & + 1. This leads to a small computational load since is small. With this sampling method, one (Zhang et al. 2017) can show that the synthetic private distribution is
P[ xaa] IT_ P[æ; 11:).
ACCURACY OF PRIVBAYES
In this section, we develop some theoretical results of the accuracy of PrivBayes. We discuss the proof of these results briefly in Section 6
4.1 STATISTICAL DISTANCES
The goal of this subsection is to establish the accuracy guarantee for PrivBayes with different post- processing methods: normalizaiion and L''pprjectioon By the term "accuracy", mean the TV or the 2 distance between the synthetic distribution and the raw data distribution, respectively. Note that the error comes from two sources: 1) approximating the raw data by Bayesian network that
4

---

Published as a conference paper at ICLR 2023
satisfies Assumption 3.1 and Assumption 3.2] 2) adding noise and post processing. The first error, however, only relies on the sparsity of the raw data. Since we aim to establish our result for general raw data, only focus on the second one. Therefore, it is natural for us to make the following assumption.
We assume the raw data distribution can be represented by Bayesian network with d vertices that satisfies Assumption 3.1 and Assumption 3.2
Assumption 4.1.
With this assumption, PrivBayes (normalization) has the following accuracy guarantee.
Theorem 4.1. Assuming that the raw dataser Boolean and satisfies Assumption 4.1 then we have
P
12
2d
log 5"
with probability at least (with respect to the randomness of the Laplace mechanism and the same below). Here P is the empirical distribution of ID and PP is the output of PrivBayes (normal- ization) with privacy budget
Proof. See Section 6 for a proof sketch.
The other post-processing method (I²-projection) we studied is also efficient. The following result verifies that PrivBayes (??-projection) enjoys the similar accuracy guarantee in terms the T,2 dis- tance. Here, with a little bit abuse of notations, we denote the 1,² distance between two distributions as the distance between their density functions.
Theorem 4.2. Assuming the raw dataset is Boolean and Assumption 4.1 is satisfied, then we have
P-P L2
PP
12d (k 1)
log
2d
TEE
with probability at least 1 5. Here P is the empirical distribution of and Tp the output of PrivBayes (L2 (projeccc))) with privacy budget
Proof. The proof similar Theorem 4.1 However it still non-trivial and we discuss in detail in Appendix B
Discussion. Theorem 4.1 and Theorem 4.2 achieves a bound that is consistent (tends to 0 as n tends to infinity) if k < (nee/") Moreover, smaller &s leads to smaller upper bounds. Since we assume that the real data and synthetic data share the same we conclude that PrivBayes achieve better performance For example, /Zhang et al. (2017) chose < the simulation. Theorem 4.1 also characterizes the reliance on the privacy budget Precisely, tighter privacy budget means better privacy guarantee, but leads to worse performance. Moreover, our rate is polynomial the dimension Comparing with directly applying the Laplace mechanism to the whole domain (see Theorem 4.3) our result shows that by heavily deploying the network structure, the Bayesian network exponentially refines the rate.
sparser real datasets. The size of k is often rather small in real application.
Theorem 4.3. Assuming that the raw datasel DD is Boolean, then we have
2d
log 2 8'
P-P
with probability at least 8. Here P the synthetic distribution generated by directly applying Laplace mechanism to the entire domain.
Proof. By the definition of Laplace mechanism, add i.i.d. Lap(1/ne) noise to all the 2d choices of P( (Za) and then normalize them. Then, Theorem 4.3 can be proved similarly as Lemma 6.1 with 2d.
5

---

Published as a conference paper at ICLR 2023
4.2 UTILITY ERRORS
In real world practice, the raw training data in supervised learning may contain sensitive information, like personal preference of users. Therefore, it is not allowed to be released to the public. An alternative is to release differentially private synthetic data instead of the raw data. A central problem the "utility" of synthetic training data, which means the evaluation of synthetic data in downstream tasks. We explain the term utility in detail below.
Consider a dataset D = {- drawn from the domain with sample size n. We denote its corresponding synthetic dataset as Ii = (x(*) Ji=l of size n. We use the empirical risk minimization (ERM) model to capture the supervised learning. Precisely, the ERM estimators for the raw dataset and the synthetic data D are defined as
Ō = arg min
Σ 8(0,z + 1=1
8EC
0ayn syn
arg min BEc
((0, (1)) XJ(O),
respectively, Here C is a convex closed set. We assume the loss function {(;, is convex on C and L-Lipschitz in æ for some L 2 The regularization term J(-) adopted to prevent over-fitting.
The model captures wide range applications. For example, given data point x(()) (u, ex) {0, 13d41, by defining the hinge loss {(0, 20) (1- (0, u.) vz) +., recover the popular support vector machine (SVM) classifier. The loss is vd + I-Lipschitz
since || / +
The utility of the synthetic dataset DD measures whether Oayn and perform similarly on the predic- tion task (Esteban et al. 2017). To be specific, the following metric is used to evaluate the utility.
1 R(0) - R(Dayn)
D) =
where R(O) - Ei (0,,x is the empirical risk on ID (Ranninn et al. 2020 Hittmeir et al. 2019)). Intuitively, the asymptotic behavior of T (T), DD) is affected by the difference between distri- butions of synthetic data and true data. This fact characterized Theorem 4.4
We first make the following assumption the bound of the loss function ((:,-), which is quite natural due to its continuity (Bassily et al. 2014).
Assumption 4.2. For any 0 C and any data point æ in Q we have [((0,x)] S
Generating synthetic dataset from PrivBayes. We still denote the raw dataset as ID and denote its empirical distribution. Its corresponding output of PrivBayes is distribution denoted as Q. To generate the synthetic training data D, we draw iidd samples from Q. The corresponding empirical distribution is denoted as Q.
With the above preparation, PrivBayes.
now ready state our result that characterizes the utility of
Theorem 4.4. If Asssuppttin and Assumption 4.2 hold and the raw dataset D Boolean, then have
log
( C()) -PPIy + +2R +
2ñ
22 +
2d
log 1
C(()+
In
+ 2Rc +
(4)
8
2n
with probability at least 1- 8. Here Ro the Rademacher complexity of the function class {a +> ((0,z) 0 E C} and C2 is positive universal constant. The term C()) is non non-negative and vanishes when X 0, namely C(0) =
Proof. See Section proof sketch.

---

Published as a conference paper at ICLR 2023
Discussion. The term C()) comes from the regularization process. C(A) 0 if no regularization applied (A = 0). In real practice, À is often much smaller than d² /nn Therefore C(A) is also relatively small. The Rademacher complexity in equation 4 comes from the sampling process.
Our result then implies that, when the sample size n and are sufficiently large and the regularization parameter À is sufficiently small, the quality loss caused by the private mechanism is rather small. In other words, private synthetic data generated by PrivBayes performs similarly to raw data in downstream learning tasks.
5 LOWER BOUND
In this section, we complete the picture by deriving lower bound for the TV-distance between synthetic private distribution and the raw data distribution.
Notations and conventions. As before, the raw dataset D is of size with empricial distribution P. The data domain is denoted as Ωt synthetic data generator randomized algorithm that sends a dataset of size n to a distribution over f. We also need the following assumption on the range of the parameters.
Assumption 5.1. We assume that d/c < < 1
The first part of this assumption allows rather wide choice of in practice. For instance, in two real datasets ACS (Ruggles et al.] 2013) and Adult (Bache & Lichman (013), the size n = 40, 000, the dimension d x 40. Then Assumption 5.1 only requires 2 1/1, 000. Moreover, the size of Ω2 is at least 24, which is clearly much larger than n. Therefore, the second part of Assumption 5. holds for real world datasets.
We now state Theorem 5. that establishes the lower bound for TV-distance.
Theorem 5.1. If Assumption 5.1 holds. then for any synthetic data generator A(.) with privacy budget e, and for any S < 1/2, there exists a dataset of size n, such that
|[(D)) Pliv -
log(6(11)
with probability at least 1 25. Here IP is the empirical distribution of D.
Proof. See Appendix D for a detialed proof.
Choosing 1/4 4 in Theorem 5.1 yields the following corollary.
Corollary 5.2. [2] 2 4 ex)(()), then for any synthetic data generator A(-) with privacy budget e, there exists dataset ID of size such that
d THE with probability at least 1/2. Here P is the empirical distribution of D.
|A()) - Pllty
Discussion and comparison. Comparison with the upper bound in Theorem 4.1 PrivBayer is sub-
optimal up to d factor. The sub-optimality is caused by the composition property of DP (the dataset is processed d times in Bayesian network) and the structure of a Bayesian network.
PROOF SKETCH FOR THE TECHNICAL RESULTS
PROOF SKETCH FOR THEBRRM
We begin with technical lemma that characterizes the normalization process. See Appendix Aor its detailed proof.
Lemma 6.1. For distribution (a1, J. ) we denote its outcome after adding i.i.d. Lap(d/ne)
noise and normalizing it as (bi, bm.). Then, for all large n and all O, it holds that
3md log
max la, b,l
nE
8
with probability at least 5.

---

Published as a conference paper at ICLR 2023
Lemma 6.1 characterizes the difference between Pz,,, II;) and P II,). However, need fur- ther analysis to establish the conditional version of Lemma 6.1 To be specific, we need to bound
((z II,) P(x I.). The following result serves for this goal.
Lemma 6.2. Consider two non-negative real vectors (01,--- ,a,) and (b ba) (not necessary to be distributions). If. for some 3 2 0, have
max aj bUو S 3
(5)
J
then, for any E {1,... s), the following result holds.
bi
(6)
Σ aj
2j
bj
2j=1
Proof. See Appendix(AAoor for detailed proof.
Combining Lemma 6.1 and Lemma 6.2 the distance between the conditional distributions is bounded in the following result.
Lemma 6.3. If D boolean and satisfies Assumption 4.1 then we have
6d2 (k: + 1)
P(zz II,) - P(x; H.)
log 8 P(I.))
with probability at least 1 6, simultaneously for all i and all choices of (xz, II:).
Proof. Setting
2*+1
5 = 2,
P(1, IT.). = P(O, IT,), d P(1, II,,, ) b2 P(O, II), 3md
3 me log
in Lemma 6.1 and Lemma 6.2 concludes the proof.
To bound the TV-distance, we begin with rewriting it in telescoping series and applying Lemma 6.3 One technical impediment for estimation is the fraction term (IL, in (7p. To address this challenge, we need to deploy the Bayesian network structure (Assumption 3.1 and Assumption 3.2) Deploying the network structure is quite technical and lengthy, we defer the detail to Appendix
6.2 PROOF SKETCH FOR THEOREM
We begin with some notations. The non-regularized estimators trained on D and D by an ERM model are denoted as 0 and 0+ 0= Formally, we define
0" == arg min BEC
1
Σ
E(0, (0))
n
i=1
1
0% = arg min
(0,,000)
dEC
ft
We further define the prediction risk with respect to certain distribution. For any distribution on Ω denoted as P. and any 0 C we define
R(O, P) = Σ P(x)
(8)
rEf
the prediction risk with respect to P. Then R(-) in 3 is equal to R(: PP).
8

---

Published as a conference paper at ICLR 2023
We ready sketch the proof. The most important step of the proof is to decompose the utility in into the following seven terms
UQQ.P)
R(O R[Osyn: P)- R[Oayn: Q)
[l(aayn Q) - R(Oaans @)) + R[Oayn: Q)) R(O syyu Q)
term (i)
term (i))
term (iii)
R(OSyn Q) R(O Q)
R(O", Q) - R(O" mo00 Q)
R(O P)]
term (vi)
term (iv)
term (V)
R(O" IP) R(O,P)
(vii)
Recall that the output of PrivBayes and Q is the empirical distribution of the samples drawn independently from Q. Here term (i) and term (vi) come from the difference between the synthetic distribution Q and the raw distribution P. They can be bounded above by the distance between the synthetic distribution and the raw one. Term (ii) and term (v) come from sampling and are bounded by classical Rademacher method. Term (iii) and term (vii) are derived from the regularization pro- cess. They combine to be the C()) term. Bounding term (iv), however, is more tricky and requires more detailed analysis. We discuss each group in detail in Appendix C
DISCUSSIONS AND FUTURE TOPICS
We establish perhaps the first statistical analysis for the accuracy and utility of Bayesian network- based data synthesis algorithms. We also derive lower bound for the accuracy to complete the picture. Compared with the lower bound, the accuracy bound we achieve is sub-optimal up to a factor. One way improve the accuracy is reduce the effects of random noise releasing the synthetic data through some post-processing procedures. However, it is still quite challenging to develop a practical algorithm based on this idea, and we leave for future work.
ACKNOWLEDGMENTS
We appreciate Prof. Ninghui Li and Dr. Zitao Li for their discussions about the background and ap- plications of marignal- data synthesis methods, which motivates us to study the corresponding theory. This research is supported by the Office of Naval Research [ONR N00014-22- 1-22800 and the National Science Foundation [NSF SCALE MoDL (2134209)).

---

Published as a conference paper at ICLR 2023
REFERENCES
John M. Abowd. The U.S. Census Bureau adopts differential privacy. KDD '18, pp. 2867, New York, NY. USA, 2018. Association for Computing Machinery. ISBN 9781450355520. doi: 10. 1145/3219819.3226077
Kevin Bache and Moshe Lichman. UCI machine learning repository. 2013.
Boaz Barak, Kamalika Chaudhuri, Cynthia Dwork, Satyen Kale, Frank McSherry, and Kunal Tal- war. Privacy, accuracy, and consistency too: holistic solution contingency table release. In Proceedings of the 26th ACM Systems, pp. 273-282, 2007.
Symposium on Principles of Database
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight enror bounds. In IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 464-473, 2014.
Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim. Practical privacy: The SuLQ framework. In Proceedings of the 24th ACM SIGMOD-SIGACT-SIG Symposium Princi- ples of Database Systems, pp. 138, 2005.
Kuntai Cai, Xiaoyu Lei, Jianxin Wei, and Xiaokui Xiao. Data synthesis via differentially private Markov random fields. Proceedings of the VLDB Endowment, 14(11):2190-230 2021.
Irit Dinur and Kobbi Nissim. Revealing information while preserving privacy. In Proceedings of the 22th ACM SIGMOD-SIGACTSSIGARRY Symposium on Principles of Database Systems, pp- 202-210, 2003.
Cynthia Dwork. Differential privacy: A survey of results. In International Conference on Theory and Applications of Models of Computation, pp. 1-19, 2008.
Cynthia Dwork and Kobbi Nissim. Privacy-preserving datamining on vertically partitioned databases. In Annual International Cryptology Conference, pp. 528-544, 2004.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference, pp. 265-284, 2006.
Cynthia Dwork, Frank McSherry, and Kunal Talwar. The price of privacy and the limits of LP decoding. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing. pp. 85-94, 2007.
Cynthia Dwork, Aleksandar Nikolov, and Kunal Talwar. Efficient algorithms for privately releasing marginals via convex relaxations. Discrete Computational Geometry, 53(3):650-673, 2015.
Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy-preserving ordinal response. In Proceedings of the 2014 ACM SIGSAC conference on computer and communications security, pp. 1054-1067. ACM, 2014.
Cristóbal Esteban, Stephanie L. Hyland, and Gunnar Rätsch. Real-valued (medical) time series generation with recurrent conditional GANs. arXiv preprint arXiv:1706. 02633, 2017.
Moritz. Hardt and Kunal Talwar. the geometry of differential privacy. In Proceedings of the 42th ACM Symposium Theory of Computing, pp. 705-714, 2010.
Markus Hittmeir, Andreas Ekelhart, and Rudolf Mayer. On the utility of synthetic data: An empirical evaluation on machine learning tasks. Proceedings of the 14th International Conference on Availability, Reliability and Security, pp. 1-6, 2019.
Noah Johnson, Joseph P Near, and Dawn Song. Practical differential privacy for SQL queries using elastic sensitivity. arXiv preprint arXiv: 776.0077,, 2017.
Michael Irwin Jordan. Learning in graphical models. MIT press, 1999.
James Jordon, Jinsung Yoon, and Mihaela van der Schaar. Measuring the quality of synthetic data for use in competitions. arXiv preprint arXiv: 1806. /345, 2018.
10

---

Published as a conference paper at ICLR 2023
Ashwin Machanavajjhala, Daniel Kifer, John Abowd, Johannes Gehrke, and Lars Vilhuber. Privacy: Theory meets practice on the map. In IEEE 24th International Conference on Data Engineering, pp. 277-286, 2008.
Ryan Mckenna, Daniel Sheldon, and Gerome Miklau, Graphical-model based estimation and infer- ence for differential privacy. In International Conference on Machine Learning, pp. 4435-4444, 2019.
Ryan McKenna, Gerome Miklau, and Daniel Sheldon. Winning the NIST contest: A scalable and general approach to differentially private synthetic data, arXiv preprint arXiv:2108.0491 2021.
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In JEEE 48th Anmual IEEE Symposium Foundations of Computer Science, pp. 94-103, 2007.
Thông T Nguyên, Xiaokui Xiao, Yin Yang, Siu Cheung Hui, Hyejin Shin, and Junbum Shin. Col- lecting and analyzing data from smart device users with local differential privacy. arXiv preprint arXiv: 05053, 2016.
Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pp. 75-84, 84, 2007.
NIST. The unlinkable data challenge. Available at https:// hatps::/www.niii
mta.zzee-caallngess.. 2018 aan 2018.
NIST. Differential privacy synthetic data challenge. Available at
www. nist.gov ctl /ts////crroeeenimoovttttttoooooe htgp://eeo..ppppiaeeoeeeeeeeeear lenges/past-prize--hhhe /
2018 8018-aifferrrtttaal-:-vvveyyyy
2019.
NIST. Differential privacy synthetic data challenge. Available at attpo::/ww..lss..oo
ct
2020 2000-dtfferrrmiial-prrvvagg
2020-2021. 2020022211..
Wahbeh Qardaji, Weining Yang, and Ninghui Li. Priview: Practical differentially private release of marginal contingency tables. In Proceedings the 2014 ACM SIGMOD International Conference on Management of Data, pp. 1435-1446, 2014.
Debbie Rankin, Michaela Black, Raymond Bond, Jonathan Wallace, Maurice Mulvenna, and Gorka Epelde. Reliability of supervised machine learning using synthetic data in health care: Model to preserve privacy for data sharing. JMIR Medical Informatics, 117):118910 2020.
Steven Ruggles, Katie Genadek, Ronald Goeken, Josiah Grover, and Matthew Sobek. Integrated public use microdata series: Version 6.0 [dataset]. Minneapolis: University of Minnesota, 23:56, 2015.
Thomas Steinke and Jonathan Ullman. Tight lower bounds for differentially private selection. In IEEE 58th Annual Symposium on Foundations of Computer Science, pp. 552-563, 2017.
The U.S. Census Bureau. New handbook on 2020 census disclosure avoidance. Avail- httpttiiin////////// /2tp////e///////
able at hhtps:: / www. wttpc/uss.ooo///brrbrrr/abbbbbba
2020 1020-census disclosure avo.laaanureeao..aaneeeeee handbook..hmm 2020.
census
awwidance
Jonathan Ullman. Answering N (2+o(1)) counting queries with differential privacy is hard. In
Proceedings the 45th Annual ACM Symposium on Theory of Computing, pp. 361-370, 2013.
Martin Wainwright, Michael I Jordan, inference. Foundations and Trends@ in Machine Learning, 1(1-2):1-305, 2008.
Graphical models, exponential families, and variational
Larry Wasserman and Shuheng Zhou. A statistical framework for differential privacy. Journal of the American Statistical Association, 105(489):375-38) 2010.
Jun Zhang, Graham Cormode, Cecilia M. Prcoopiuc, Divesh Srivastava, and Xiaokui Xiao. PrivBayes: Private data release via Bayesian networks. ACM Transactions on Database Systems, 02(4):1-41) 2017.
11

---

Published as a conference paper at ICLR 2023
Zhikun Zhang, Tianhao Wang, Ninghui Li, Jean Honorio, Michael Backes, Shibo He, Jiming Chen, and Yang Zhang. Privsyn: Differentially private data synthesis. In 30th USENIX Security Sympo- shmm, pp. 929-946, 2021.
12


Reviews:
[{"review_id": "ySNm41h5kIC", "reviewer": "Reviewer_BqvB", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper tackles the general problem of synthetic data estimation under differential privacy (DP). Specifically, the authors prove upper and lower bounds on DP estimation of PrivBayes, a marginal-based Bayesian network synthetic data generation method. More specifically, the authors prove upper-bounds on the total variation and L2 distance between the estimated distribution and the true distribution under the assumption that the raw data is generated from a graph with causal edges and bounded number of parent nodes for each node. The authors also show utility upper bounds, as well as total variation lower bounds.", "summary_of_the_review": "Overall I think the paper provides interesting bounds on a classical mechanism for synthetic data generation, PrivBayes. I am a bit on the fence for a general recommendation as I am not 100% familiar with the synthetic data literature but I lean towards borderline+.", "strength_and_weaknesses": "Strengths\n- The paper tackles an interesting problem, synthetic data generation under differential privacy\n- The paper is clearly written and relatively straightforward to follow\n- The bounds provide an interesting picture on the dependency to various factors (size of training data n, dimension d, 'breadth' of the model k, budget epsilon, etc.)\n\nWeaknesses\n- the upper bound seems rather loose. For example, theorem 4.1 depends exponentially on k. If we plug n=40k, d=40 and epsilon=10 which are generarous estimates, we get 12 d^2/(n*epsilon) ~ 0.05 so with k=3 the bounds becomes vacuous (and that's without looking at the log factor). ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "KCjdIEQaoA", "reviewer": "Reviewer_sYaP", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper analyzes the accuracy of PrivBayes by giving upper bounds on the distances between real and synthetic data and on utility errors of synthetic data from downstream supervised learning tasks.  The authors also proved the lower bound for total variation distance for \\epsilon-DP synthetic data generator.", "summary_of_the_review": "In general, the findings are interesting, and the work is well-supported and well-organized. Although the results leave rooms for further improvement, I would recommend this paper to be accepted.\n\n", "strength_and_weaknesses": "The authors derived three novel bounds which has not been carefully studied before. I found the proofs are compelling and the well-conveyed. The authors deliver the proofs clearly and they bound the utility errors by neatly splitting the errors into several parts.\n\nHowever, the authors only derived new bounds under total variation distance and L^2 distance. Perhaps more statistical distances should be employed to evaluate the synthetic data for higher completeness of the paper.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "7EmMmsQuM72", "reviewer": "Reviewer_PzT1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies the problem of Bayesian structure based synthetic data generation and its theoretical guarantees with respect to (probability) distance from the real data. Also, lower bounds for the TV distances between the two distributions is provided and differ by a factor of dimension d. ", "summary_of_the_review": "Overall, the paper studies an important problem setting by providing rigorous theoretical guarantees for synthetic data generation. I have some questions which I hope to discuss with the authors.  ", "strength_and_weaknesses": "Pros:\n     (A) Establishes the quality of the synthetic datasets by providing concrete distance upper-bounds on the generated datasets which are O(d^2 2^k/n) ignoring log factors and setting epsilon to 1. Similarly, utility of the datasets is provided for the downstream tasks. \n     (B) Lower bounds are also provided for the hypercube setting and is O(d/n). The suboptimality arises due to the composition component of DP. \nCons:\n\n   (i) While the theoretical guarantees that are shown in the paper are nice, it is not clear how tight they are? For typical values of k, d and n the values seem\nto be way larger than 1 and not entirely useful?\n\n   (ii) Experiments showing the tightness of the lower and upper bounds on real-world datasets would have been helpful in understanding the strengths and limitations of the theory. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "45EL5OsTgw", "reviewer": "Reviewer_mQvM", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "\nAuthors consider the case where the synthetic data distribution can be represented by a Bayesian network, while the raw data distribution is approximated by a collection of low-dimensional marginals. Differential privacy (DP) is guaranteed by introducing random noise to each low-dimensional marginal distribution. Authors study DP data synthesis algorithms based on Bayesian networks (BN) from a statistical perspective. \n", "summary_of_the_review": "Restriction to just Boolean data is a major limitation. Other than that, there are positive points about this paper. \n\n\nRevised report: I had given a score of 5 (marginally below acceptance) initially.  Given the clear answers provided by the authors, especially to the main question I had, i am happy to change my recommendation and now recommend acceptance.", "strength_and_weaknesses": "Strengths:\n\n\nAuthors have a good grasp of some of the challenges of differentially private computations in the context of the paper. The paper is generally well-written. The framework of using a BN for distribution representation is sensible n many applications, hence there is merit to the problem under study. \n\n\nWeakness:\n\nThe paper only focuses on Boolean data. There is an aside claim that it can be generalized to any categorical data with finite support, but this extension is not clear from the paper. Also, it does not seem that the main steps would extend easily without considerable problems related to scaling of the computations. It is not clear to me whether the BN is estimated from the data, or is considered known. If it is estimated from the data, is the estimation algorithm differentially private? \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster