Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 
strength_and_weaknesses: Pros:
     (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. 
     (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. 
Cons:

   (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
to be way larger than 1 and not entirely useful?

   (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. 

clarity,_quality,_novelty_and_reproducibility: The paper is pretty clear on its contributions with proof sketches for the main results sprinkled throughout the main body. The problem setting is well motivated and the novelty is in deriving rigorous guarantees.  

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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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.

However, 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.


clarity,_quality,_novelty_and_reproducibility: Yes
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: 
Authors 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. 

strength_and_weaknesses: Strengths:


Authors 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. 


Weakness:

The 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? 

clarity,_quality,_novelty_and_reproducibility: The paper is clearly written, the quality of the empirical work seems fine but there is a lack of adequate theoretical developments. The algorithm may have some elements of novelty, and the results look reproducible.

summary_of_the_review: Restriction to just Boolean data is a major limitation. Other than that, there are positive points about this paper. 


Revised 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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
strength_and_weaknesses: Strengths
- The paper tackles an interesting problem, synthetic data generation under differential privacy
- The paper is clearly written and relatively straightforward to follow
- 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.)

Weaknesses
- 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). 
clarity,_quality,_novelty_and_reproducibility: The paper is clear and well-written. To the best of my knowledge, this statistical analysis of PrivBayes is new.
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+.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies Bayesian differentially private (DP) synthetic data generation. In this work, synthetic data is generated via Bayesian Network (BN) while raw data is approximated by a set of low-dimensional marginals. 

Generating synthetic data in a privacy preserving manner is an important and timely problem with far-reaching practical impacts. The authors provide a set of interesting results. They give formal accuracy guarantees for DP BN-based algorithms in terms of upper bounds on the Total Variation (TV) and L_2 distance between the distributions of the raw and synthetic data. The authors also establish a lower bound on TV-based accuracy of any pure DP algorithm for synthetic data generation. The paper is also well written. There is a general consensus among the reviewers that the formal results of this work are interesting and useful. 
justification_for_why_not_higher_score: The contributions are above the bar of acceptance but they are not of a profound impact and/or wide interest to merit an oral or spotlight slot. 
justification_for_why_not_lower_score: The paper makes clear contributions and is above the bar of acceptance.
Decision: Accept: poster