Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper has two main contributions:

1) It proposes a unifying framework called "Adaptive Measurements" that covers many differentially private synthetic data generation algorithms and show how these algorithms can be derived by modifying the loss function and distributional family.

2) Based on the above framework, two specific synthetic data generation algorithms called Private Entropy Projection (PEP) and Generative networks with Exponential Mechanism (GEM) have been proposed. Since PEP attempts to explicitly model the data distribution, it does not scale well to higher dimensions. GEM uses the well-known generative neural networks to overcome the above problem and can also effectively use public data for good initialization.
main_review: 1) One of the main problems with the paper is that too many critical details have been pushed to the Appendix. For instance, the proof sketch of Theorem 1 must be included as part of the main text because it is not clear how the adaptive measurements mechanism ensures differential privacy. The paper should also explain what concentrated DP means from a practical standpoint and what level of privacy budget is acceptable. Similarly, the evaluation metric "max error" should also be defined and acceptable values of max error should be reported. Without such details, it would be very difficult for a practitioner to judge if the proposed algorithms are useful in real-world applications.

2) The differences between PEP and the MWEM schemes are not very clear. The paper simply brushes it off with the statement that adaptively assigning weights to past queries and measurements enables PEP to have faster convergence and better accuracy. What are the challenges and limitations in adaptive weight assignment?

3) What is the impact of the generator architecture G on the performance of the GEM scheme and how to choose the right architecture for a given problem?
  
limitations_and_societal_impact: Yes, both the limitations and societal impact have been addressed adequately.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The authors unify several algorithms for DP synthetic data generation for query release. Using this framework they create two algorithms, private entropy projection (PEP) and generative networks with the exponential mechanism (GEM). Then they empirically evaluate their algorithms in publicly available datasets and show that their algorithms (mostly) outperform existing ones. They also show how GEM can use public data to improve its accuracy.

main_review: Creating synthetic datasets for answering queries is an old and important problem in the DP literature. There exists excellent work on this problem and this paper not only manages to unify it but also improve upon it. I did not read all the proofs but what I read was technically correct. The paper very well written, it is easy to read and follow. Moreover, the relevant literature is discussed adequately. I also really appreciate the honest Limitations and Broader Impacts subsections. 

Minor issues:
Line 91, typo. “Lete” 
Line 149: “where describe” -> where we describe ?
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper tackles the problem of synthetic data generation for query release. First, it presents a general algorithmic framework (Adaptive measurements) for the task, and interprets a long line of prior work under this lense. At a high level, these works solve the min max problem in Equation 1. 

Given this formulation, the paper proposes two algorithms, PEP and GEM. PEP selects a maximum entropy distribution to minimize the error for a given query set by solving the dual of the constrained optimization problem. They offer an iterative algorithm for this.  To avoid the exponential runtime of approaches like PEP (because they maintain a distribution over entire data domains), the paper also proposes GEM, which uses a generator network to represent this high dimensional space.  GEM can easily incorporate public data (with various missingness) by using it for pretraining. 

Empirically, GEM outperforms prior work in accuracy to privacy tradeoffs on ACS and the adult datasets, and is more robust to domain shift in the public data than PMW or PEP. This gain is most pronounced when the data is high dimensional.

main_review: Originality / Significance:
This paper unifies a large set of related algorithms under a single framework, and offers a useful new algorithm, GEM that improves over prior work in data generation for query release. GEM can naturally incorporate public datasets more robustly than prior work like PMWpub.  This study seems broadly valuable for data generation for query release.

Quality:
The experiments in this paper supported the core claims and adequately demonstrated the value of the method and when we would expect the method to help (i.e high dimensional data). 

Clarity:
As a whole, the paper was fairly well written and has a detailed appendix, but I think it could benefit from expanded introductions through the main text  to make the work more accessible to the broader Neurips audience.

For instance, through the introduction, related work and abstract, the paper mentions MWEM without defining it, which makes the work less clear. This is only defined in page 4.  Giving a high level overview of how this method works earlier would make the paper more clear. Also, are there scenarios where leveraging PEP is preferred to GEM? It wasn’t clear to me through the results or discussion why both algorithms are highlighted, as GEM can both handle higher dimensional data and various public data sources. 

limitations_and_societal_impact: The authors adequately note their limitations and possible ethical concerns (i.e known issues of DP and fairness).
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: # Summary of contributions

The paper studies the problem of synthesizing differentially private (DP) data for query release. Here we are given a sensitive dataset $P$ together with a set $\mathcal{Q}$ of queries of interest. The goal is to generate a DP synthetic dataset $D$ so that answering the queries using $D$ gives similar answers to those of $P$; more formally, we want to minimize the maximum error across the queries, i.e. $\max_{q \in \mathcal{Q}} |q(P) - q(D)|$. Several works have proposed algorithms for this problem, including MWEM [Hardt et al., NeurIPS'12] and FEM [Vietri et al., ICML'20].

The first contribution of the paper is in observing that essentially the previously proposed algorithms all fit into a single framework which they call "Adaptive Measurements". Specifically, the algorithm proceeds in iterations and, in each iteration, it uses the exponential mechanism to select one or more queries, asks for noisy values of those queries and it then updates the current synthetic dataset $D$ by minimizing some objective (which involves the answers to the queries so far and the current guess dataset).

With the above in mind, the authors then decide a new algorithm which fits into this framework called Private Entropy Projection (PEP) algorithm. At each step, PEP tries to find the distribution $D$ with maximum entropy among those whose max error w.r.t. the noisy measurements is at most $\gamma$ for some parameter $\gamma$. The authors note that PEP also gives exponentially weighted distributions, similar to MWEM, but the weights are more elaborated. Empirically, the authors show that PEP performs better than MWEM when $\epsilon$ is sufficiently large (and performs similarly for small $\epsilon$) on reduced versions of ADULT and ACS datasets for 3-way marginal queries.

The reason a reduced version of those datasets are used is because the original datasets have high-dimension, which is infeasible for MWEM or PEP since they have to keep the entire distribution explicitly. To overcome this, the authors propose a different algorithm called GEM which instead assume that the distribution is generated to some network $G_\theta$ with parameter $\theta$ (assuming that the inputs to the network is i.i.d. Gaussian). This can help reduce the computational cost dramatically since now only the network parameters $\theta$ is needed to be maintained. Here, GEM still works in the "Adaptive Measurements" framework and the authors use gradient descent to minimize the $\ell_1$ loss w.r.t. the noisy measurements so far. Note that this might not be easily differentiable for generic queries; fortunately, for k-way marginal queries, the authors point out that they are just product of the network's outputs and as a result the gradient can be easily found.

Finally, the authors consider the setting where there is some public data which one hopes to use to improve the quality of the synthetic dataset. Previous state-of-the-art called PMW$^{Pub}$ [Liu et al., 2021] simply uses limits the distribution to only those on the _support_ of the public data and runs MWEM. This has several limitations, such as when the support of the public data is not sufficient to express the sensitive data, or when some features are missing in the public dataset. The authors show that a modified version of GEM (called GEM$^{Pub}$) is more amenable for these cases: just use the public data to find an initial generator network, and then proceed with the GEM algorithm as usual. They demonstrate that this approach indeed works well in practice: although the performances of GEM$^{Pub}$ and PMW$^{Pub}$ are similar for large & similarly-distributed public data, GEM$^{Pub}$ significantly outperforms PMW$^{Pub}$ when public data is incomplete or its support not closely resembling the sensitive data.
main_review: # Evaluation

## Strengths

- The GEM algorithm is surprisingly intuitive and also works very well in the public-assisted setting. This can potentially be helpful as many recent research works in DP have been trying to exploit public data, but as far as I am aware of, none of the proposed solutions is as robust as the new GEM$^{Pub}$ algorithm.

## Weaknesses

- My main criticism is in regards to the authors' descriptions of their algorithms. There are often confusing, imprecise and sometimes inconsistent. Please see below when I go into more detail on this issue for the PEP algorithm. (A summary is that the algorithm described in the main body is not exactly the same as that described in the appendix which itself is also slightly different from what was actually implemented.)
- There is no theoretical utility guarantee for PEP. This makes it much harder to compare to previous algorithms like MWEM, FEM or DualQuery, all of which have good formal guarantees on the maximum error. (Note that the lack of theoretical utility guarantee for GEM is more understandable since it might require complicated assumption on the generator network, but the worst-case guarantee for PEP should exist without any additional assumption.)
- There are also quite a fair bit of typos & errors in writing. For example, their privacy proof completely forgets to take $k$ (number of queries selected per stage) into account altogether.

## Recommendation

Overall, although I think that the paper should be significantly revised (so that the algorithm descriptions are more clear & consistent) and that theoretical guarantees should be derived for PEP, I still think the new public-assisted approach can be useful both to the research community and in practice.

# Detailed Comments

- **Issues with PEP Algorithm**:
  - First of all, in the main body the selection of $D$ is described as maximizing the entropy subject to the constraints $|\tilde{a}_i - \tilde{q}_i(D)| \leq \gamma$. What happens if the constraints cannot be satisfied (i.e. when $\tilde{a}_i$ has a lot of noise)? Also, $\gamma$ is never specified anywhere; how is it selected?
  - Secondly, the algorithm you are using (Algorithm 2) is only trying to fix one of these constraints at a time. I don't see why this should even converge, let alone have a good convergence rate.
  - Finally, your code (`project` function in `pep.py`) does not even take $\gamma$ at all. It just tries to perform correct for the worst $\tilde{q}_i$ for a given number of iterations. It is unclear to me what kind of objective this is even trying to optimize.
- **Issue with Privacy Analysis**: The noise setting in Section 3.1 and proof of Theorem 1 in Appendix A do not take $k$ (number of queries selected per iteration) into account. Please fix this.

Minor comments:
- **Indices in Algorithm 1 vs in other places**: Please check the indices of $\tilde{q}, \tilde{a}$ and make sure they are all consistent. For example, the indices in Algorithm 1 here are $t,i$, but in MWEM (line 135-136), the index is $i$ and the sum is over $i = 1$ to $t$. These are pretty confusing; I think $i$ should be changed to $t$ here and $t$ to $T$. Similar inconsistencies can be found elsewhere too.
limitations_and_societal_impact: I do not see any significant negative social impact of this work. One thing that might be useful is to discuss the issue of bias that might arise in the public-assisted setting.
review_title: null

Meta-review: The paper got overall strong feedback from the reviewers. There were a few concerns regarding the presentation, once addressed will make the paper stronger. Some of those are:

1. A more formal treatment of the Private Entropy Projection algorithm. In particular the distinction between the constrained version, and the Lagrangian formulation.

2. The lack of theoretical analysis of utility. Since almost all the prior works have a formal utility analysis, it is important for the authors to point out any technical difficulty towards proving a formal analysis.
Decision: Accept (Poster)