Iterative Methods for Private Synthetic Data: Unifying Framework and New Methods
Authors: Terrance Liu
Giuseppe Vietri
Steven Wu
Venue: NeurIPS 2021 Poster (2021)
Keywords: Privacy
Differential Privacy
Machine Learning
Deep Learning
Synthetic Data
Query Release

Abstract: We study private synthetic data generation for query release, where the goal is to construct a sanitized version of a sensitive dataset, subject to differential privacy, that approximately preserves the answers to a large collection of statistical queries. We first present an algorithmic framework that unifies a long line of iterative algorithms in the literature. Under this framework, we propose two new methods. The first method, private entropy projection (PEP), can be viewed as an advanced variant of MWEM that adaptively reuses past query measurements to boost accuracy. Our second method, generative networks with the exponential mechanism (GEM), circumvents computational bottlenecks in algorithms such as MWEM and PEP by optimizing over generative models parameterized by neural networks, which capture a rich family of distributions while enabling fast gradient-based optimization. We demonstrate that PEP and GEM empirically outperform existing algorithms. Furthermore, we show that GEM nicely incorporates prior information from public data while overcoming limitations of PMW^Pub, the existing state-of-the-art method that also leverages public data.

Iterative Methods for Private Synthetic Data: Unifying Framework and New Methods
Terrance Liu" Carnegie Mellon University Pittsburgh, PA 15213 perranc@@andree cmu cmu.edu
Giuseppe Vietri' University of Minnesota Minneapolis, MN 55455 vietr002@umn.co edu
Zhiwei Steven Wu Carnegie Mellon University Pittsburgh. PA 15213
zstevenvu@cmu. edu
Abstract
We study private synthetic data generation for query release, where the goal construct sanitized version of a sensitive dataset, subject to differential privacy, that approximately preserves the answers to a large collection statistical queries. We first present an algorithmic framework that unifies long line of iterative al- gorithms in the literature. Under this framework, we propose two new methods. Our first method, generative networks with the exponential mechanism (GEM), cir- cumvents computational bottlenecks in algorithms such as MWEM by optimizing over generative models parameterized by neural networks, which capture a rich family of distributions while enabling fast gradient-based optimization. The second method, private entropy projection (PEP), can be viewed of MWEM that adaptively reuses past query measurements to boost accuracy. We demonstrate that GEM and PEP empirically outperform existing algorithms. Fur- thermore, we show that GEM nicely incorporates prior information from public data while overcoming limitations of PMWPub the existing state-of sttte-ofthhe-ee method that also leverages public data.
advanced variant
Introduction
As the collection and analyses of sensitive data become more prevalent, there an increasing need to protect individuals' private information. Differential privacy [15] is rigorous and meaningful criterion for privacy preservation that enables quantifiable trade-offs between privacy and accu- racy. In recent years, there has been wave of practical deployments of differential privacy across organizations such as Google, Apple, and most notably, the U.S. Census Bureau [3].
In this paper, we study the problem of differentially private query release: given a large collection of statistical queries, the goal release approximate answers subject the constraint of differential privacy. Query release has been one of the most fundamental and practically relevant problems in differential privacy. For example, the release summary data from the 2020 U.S. Decennial Census can be framed as query release problem. We focus on the approach of synthetic data generation- -tha is, generate a privacy-preserving "fake" dataset, or more generally a representation of probability distribution, that approximates all statistical queries of interest. Compared to simple Gaussian or Laplace mechanisms that perturb the answers directly, synthetic data methods can provably answer exponentially larger collection of queries with non-trivial accuracy. However, their statistical advantage also comes with a computational cost. Prior work has shown that achicving better accuracy than simple Gaussian perturbation is intractable in the worst even for the simple query class of 2-way marginals that release the marginal distributions for all pairs attributes [38]
* First two authors contributed equally.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Despite its worst-case intractability, there has been recent surge of work on practical algorithms for generating private synthetic data. Even though they differ substantially in details, these algorithms share the same iterative form that maintains and improves probability distribution over the data domain: identifying small collection of high-error queries each round and updating the distribution to reduce these errors. Inspired by this observation, we present a unifying algorithmic framework that captures these methods. Furthermore, we develop two new algorithms, GEM and PEP, and extend the former to the setting in which public data is available. We summarize our contributions below:
Unifying algorithmic framework. We provide a framework that captures existing iterative algo- rithms and their variations. At a high level, algorithms under this framework maintain a probability distribution over the data domain and improve it over rounds by optimizing a given loss function. We therefore argue that under this framework, the optimization procedures of each method can be reduced what loss function is minimized and how its distributional family is parameterized. For example, we can recover existing methods by specifying choices of loss functions- -ee rederive MWEM (21) using entropy-regularizeed linear loss, FEM 440] using linear loss with a linear perturbation, and DualQuery [19] with a simple linear loss. Lastly, our framework lends itself naturally to softmax variant of RAP [5], which we show outperforms RAP itself
Generative networks with the exponential mechanism (GEM). GEM is inspired by MWEM. which attains worst-case theoretical guarantees that are nearly information-theortiicaal optimal [[]] However, MWEM maintains a joint distribution over the data domain, resulting in a runtime that
is exponential in the dimension of the data. GEM avoids this fundamental issue by optimizing the
absolute loss over a set of generative models parameterized by neural networks. We empirically demonstrate that in the high-dimensional regime, GEM outperforms all competing methods.
Private Entropy Projection (PEP). The second algorithm we propose is PEP, which can be viewed as a more advanced version of MWEM with an adaptive and optimized learning rate. We show that PEP minimizes regularized exponential loss function that be efficiently optimized using an iterative procedure. Moreover, we show that PEP monotonically decreases the error over rounds and empirically find that it achieves higher accuracy and faster convergence than MWEM.
Incorporating public data. Finally, we consider extensions of our methods that incorporate prior information in publicly available datasets (e.g., previous data releases from the American Community Survey (ACS) prior to their differential privacy deployment). While Liu al. (26 has established PMWPub as a state-of-the-art method for incorporating public data into private query release, we discuss how limitations of their algorithm prevent PMWPub from effectively using certain public datasets. We then demonstrate empirically that GEM circumvents such issues via simple pretraining, achieving max errors on 2018 ACS data for Pennsylvania (at E = 1) 9.23x lower than PMWPub when using 2018 ACS data for California as the public dataset.
1.1 Related work
Beginning with the seminal work of Blum al. 9. long line of theoretical work has studied private synthetic data for query release [33 22 20 While this body of work establishes optimal statistical rates for this problem, their proposed algorithms, including MWEM [2]. typically have
running time exponential in the dimension of the data. While the worst-case exponential running time
is necessary (given known lower bounds [T6] 36 39) recent line of work on practical algorithms
leverage optimization heuristics to tackle such computational bottlenecks [19
40 5] In particular,
DualQuery [19] and FEM [40] leverage integer program solvers solve their NP-hard subroutines.
and RAP (S] uses gradient-based methods to solve its projection step. In Section 3 we demonstrate how these algorithms can be viewed as special cases of our algorithmic framework. Our work also relates to a growing line of work that use public data for private data analyses (6 6,440 7 For query release, our algorithm, GEM, improves upon the ofate-of-the-arr method, PMW 266,, which is more limited in the range of public datasets it can utilize. Finally, our method GEM is related to line
We note that Aydore al. 5 have since updated the original version //atta:///rxiv.. wwtp:/o////p/pp////////// 06641v1. pdf) of their work to include a modified version of RAP that leverages SparseMax 27]. similar to way in which the softmax function is applied in our proposed baseline, RApsotmmax
2

---

of work on differentially private GANs 8
44 30 42
However, these methods focus generating
synthetic data for simple downstream machine learning tasks rather than for query release.
Beyond synthetic data, a line of work on query release studies "data-independent" mechanisms (a term formulated in Edmonds et al. (17) that perturb the query answers with noise drawn from a data-independent distribution (that may depend on the query class). This class of algorithms includes the matrix mechanism (25). the high-dimensional matrix mechanism (HDMM) (28) the
projection mechanism [3I] and more generally the class of factorization mechanisms [17] In
addition, McKenna et provide an algorithm that can further reduce query error by learning a probabilistic graphical model based on the noisy query answers released by privacy mechanisms.
2
Preliminaries
Let X denote finite d-dimensional data domain (e.g.. X' {0, 1J49. Lete U be the uniform distribution over the domain X. Throughout this work, we assume a private dataset P that contains the data of individuals. For any X, we represent P(x) as the normalized frequency of æ in dataset P such that EEEx P(x) = 1. One can think dataset either as a multi-set of items from X
distribution over X.
We consider the problem of accurately answering an extensive collection of linear statistical queries (also known as counting queries) about dataset. Given a finite set of queries Q, our goal is to find synthetic dataset D such that the maximum error over all queries in Q, defined as max (g(P) (D)), is as small possible. For example, many people in a dataset have brown eyes? More formally, statistical linear query qs is defined by predicate function & X + {0, 1}. as qu (D) Ezex ((x) for any normalized dataset D. Below, we define an important, and general class of linear statistical queries called k-way marginals. Definition 1 (k-way marginal). Let the data universe with d categorical attributes be X = (X1 X ... x Xa). where each X, is the discrete domain of the ith attribute Ag. k-way marginal query is defined by a subset S C [d] of k features (i.e., [S| k) plus target value llies for each feature in S. Then the marginal query (s.y(1) (x) is given by:
may query a dataset by asking the following: how
S (x)
II 1 (a+ = =14) iE
where I; X₁ means the i-th attribute of record X. Each marginal has a total of II queries, and we define workload as set of marginal queries.
[X]
We consider algorithms that input dataset P and produce randomized outputs that depend on the data. The output of a randomized mechanism M X + R is privacy preserving computation if satisfies differential privacy (DP) [15]. We say that two datasets are neighboring if they differ in at most the data of one individual.
X R. is (c,0) 6)- differentially privacy, for all neighboring datasets P, P' (i.e., differing on a single person), and all measurable subsets S C R we have:
Definition 2 (Differential privacy 15).. A randomized mechanism M
Pr Pr[M(P) E EP E 5
Finally, related notion of privacy is called concentrated differential privacy (?CDP) 14 10 which enables cleaner composition analyses for privacy.
Definition 3 (Concentrated DP, Dwork and Rothblum 14) Bun and Steinke (0). A randomized
mechanism M X + R J if for all neighboring datasets P, P (i.e., differing on single person), for all a E (o),
R. (M(P) II M(P)) S S
where Ry (M(P) M(P')) is the Rényi divergence between the distributions M(P) and M(P)).
3 A Unifying Framework for Private Query Release
In this work, we consider the problem of finding distribution some family of distributions that achieves low error on all queries. More formally, given private dataset P and query set Q,
3

---

solve an optimization problem of the form:
min max (q(P) - c(D)
DED gEQ
In Algorithm| [ we introduce Adaptive Measurements, which serves as general framework for solving ( At each round the framework uses private selection mechanism choose queries Q. = - ] with higher error from the set Q. then obtains noisy measurements for the queries, which we denote by A, {ār.1,.... Tz J. where Te,; = Tr. žτ, and žτ,i is random Laplace or Gaussian noise. Finally, it updates its approximating distribution D., subject to loss function L that depends on Q _ Qi and A = U A, We note that serves as surrogate problem to ① in the sense that the solution of minDeD L(D) is approximate solution for (I. We list below the corresponding loss functions for various algorithms the literature of differentially private synthetic data. (We defer the derivation of these loss functions to the appendix.)
MWEM from Hardt et al. [22
MWEM solves an entropy regularized minimization problem:
C MWEM (D,
LD,Que Uua Aua) ΣΣ Σ - 1=1
D((x)
log D(x)
BEX
We note that PMWPub (26) optimizes the same problem but restricts D to distributions over the public data domain while initializing Do to the public data distribution.
DualQuery from Gaboardi et al. [19 At each round f, DualQuery samples queries (Q: 1. )) from Qe and outputs D, that minimizes the the following loss function:
DualQuery (D,
Σ (D) 1=1
FEM from Vietri al. 40 The algorithm FEM employs a follow the perturbed leader strategy, where round f, FEM chooses the next distribution by solving:
FEM (D. Q1.))
Th (D) + E. ((2, n))
We note that RAP follows the basic structure of Adaptive Measurements, where iteration i, RAP solves the following optimization problem:
RApsoftmax adapted from Aydore et al.
5
RAP (D, Qua,AAA
Σ (Q) 2z,5)
However, rather than outputting dataset that can be expressed as some distribution over X, RAP projects the noisy measurements onto a continuous relaxation of the binarized feature space of X. outputting D E [1 xd (where n'' is an additional parameter). Therefore to adapt RAP to Adaptive Measurements, we propose a new baseline algorithm that applies softmax function instead of clipping each dimension of D to be between -1 and 1. For more details, refer to Section 4 and Appendix B, where describe how softmax is applied GEM in the same way. With this slight modification, this algorithm, which denote RApsoltmax fits nicely into the

---

Adaptive Measurements framework in which we output synthetic dataset drawn from some probabilistic family of distributions D (M) e R
Algorithm 1: Adaptive Measurements
Input:
Private dataset P with records, set of linear queries Q, distributional family D, loss functions L, number of iterations T
Initialize distribution Do
for t= 1,..., T do
Sample: For E [kt] choose Ht.s using a differentially private selection mechanism. Measure: For i E [k), let (z, Tt. (P) + zt,; where is Gaussian or Laplace noise
Update: Let Q. {4.,1...... (0......,..... 3.,k and A {ā āt,k.. Update distribution D:
D, - arg min DED (D-1. Que, A1x))
where Qne - 2 and An U A.. end
Output H (IDi)Eso) where H is some function over all distributions D, (such as the average)
Finally, we note that in addition the loss function L, key component that differentiates algorithms under this framework is the distributional family 'D that the output of each algorithm belongs to. We refer readers Appendix A.2 where we describe in more detail how existing algorithms fit into our general framework under different choices of L. and D.
3.1 Privacy analysis
We present the privacy analysis of the Adaptive Measurements framework while assuming that the exponential and Gaussian mechanism are used for the private sample and noisy measure steps respectively. More specifically, suppose that (1) sample queries using the exponential mechanism with the score function:
Pr lār. g) x exp (azunlg(P)) g(D:-1)I)
and (2) measure the answer to each query by adding Gaussian noise
21, N (o. a0
N
Letting 5o (1a))))-))) and (0, 1) be a privacy allocation hyperparameter (higher values of a allocate more privacy budget to the exponential mechanism), we present the following theorem: Theorem 1. When run with privacy parameter Adaptive Measurements satisfies p-zCDP. Moreover for all > 0, Adaptive Measurements satisfies(E(E), 8) differential privacy, where E(0) 2 1og(1
Proof sketch. Fix T 2 1 and E (0, (i) At each iteration t E [T]. Adaptive Measurements runs the exponential mechanism times with parameter 20cØ, which satisfies (2as,)² = & (as,)².
zCDP 12), and the Gaussian mechanism & times with parameter (1 a) which satisfies [1 - -CDP [10]. (ii) using the composition theorem for concentrated differential privacy
100, Adaptive Measurements satisfies &T [a2 (1 a} =t-2CDP after T iterations. (ii) Set-
ting Ep
xT(a)=(1-0) we conclude that Adaptive Measurements satisfies p>cCDP, which
2p
turn implies
(o (0+2 (122ll/l1/)) -differrential privacy for [10]
4 Overcoming Computational Intractability with Generative Networks
We introduce GEM (Generative Networks with the Exponential Mechanism), which optimizes over past queries improve accuracy by training a generator network Go implicitly learn distribution
5

---

of the data domain, where Gg can be any neural network parametrized by weights 8. As a result, our method GEM can compactly represent a distribution for any data domain while enabling fast, gradient-based optimization via auto-differentiation frameworks 132
Concretely, Go takes random Gaussian noise vectors input and outputs a representation Ga(z) of a product distribution over the data domain. Specifically, this product distribution representation takes the form of a d' d'-dimensional probability vector Gø(z) E [0, 1]" where d' is the dimension of the data one-hot encoding and each coordinate Gg Gş(2); (2); corresponds to the marginal probability of a categorical variable taking specific value. To obtain this probability vector, we choose softmax as the activation function for the output layer in Gg. Therefore, for any fixed weights 6, Go defines a distribution over X' through the generative process that draws random N (0, σ²T) and then outputs random x drawn from the product distribution Gz We will denote this distribution as Po-
To define the loss function for GEM, we require that it be differentiable so that we can use gradient- based methods to optimize Gg. Therefore, we need obtain differentiable variant of q. Recall first that a query is defined by some predicate function Ø X' + {0, } over the data domain X' that evaluates over a single row X. We observe then that one can extend any statistical query q to be a function that maps a distribution Pe over X to value in [0, 1]:
(P)) = E [o(x)] = Σ )())Po(x)
(2)
xEN
Note that any statistical query is then differentiable w.r.t. 0:
k d 1 k 3=1
Ve Vola = E vePo(r)0(z) = EZ,N(O.TL)
<( Vo
(GG())))
TE
SEX
and we can compute stochastic gradients of q w.r.t. 0 with random noise samples z. This also allows us to derive differentiable loss function in the Adaptive Measurements framework. In each round 1, given set of selected queries Q1:A and their noisy measurements AL:, GEM minimizes the following lloss::
c GEM (1, Ane)
Σ
(P((P)) a,l-
where ã. E Qu. and ā. E A
In general, we can optimize cGE by running stochastic (sub)-gradient descent. However, we remark that gradient computation can be expensive since obtaining low-variance gradient estimate often requires calculating VzPa(z) for a large number of z. In Appendix B we include the stochastic gradient derivation for GEM and briefly discuss how an alternative approach from reinforcement
learning.
For many query classes, however, there exists some closed-form, differentiable function surrogate to (3) that evaluates (z)( directly without operating over all æ E X. Concretely, we say that for certain query classes, there exists some representation fa A (X') > [0. 1] for q that operates in the probability space of X' and is also differentiable.
In this work, we implement GEM to answer k-way marginal queries. which have been one of the most important query classes for the query release literature [22 40 19 (66 and provides a differentiable form when extended to be function over distributions. In particular, we show that k-way marginals can be rewritten as product queries (which are differentiable).
Definition 4 (Product query). Let p E Rd' be a representation of a dataset (in the one-hot encoded space), and let S [d'] be some subset of dimensions of p. Then we define a product query Iss as
fs(p) = II Pj
(4)
jES
A k-way marginal query & can then be rewritten as 44) where p = Gz(z) and is the subset of dimensions corresponding to the attributes A and target values y that are specified by é (Definition Dp. Thus, we can write any marginal query as I Iiess Go(z);, which is differentiable w.r.t. Go (and Therefore differentiable w.r.t weights by chain rule). Gradient-basee optimization techniques can
then be used to solve 33: the exact details of our implementation can be found in Appendix B

---

Maximum-Entropy Projection Algorithm
Next, we propose PEP (Private Entropy Projection) under the framework Adaptive Measurements. Similar to MWEM, PEP employs the maximum entropy principle, which also recovers a synthetic data distribution in the exponential family. However, since PEP adaptively assigns weights to past queries and measurements, it has faster convergence and better accuracy than MWEM. PEP's loss function Adaptive Measurements can be derived through a constrained maximum entropy optimization problem. At each round t, given set of selected queries Q1 and their noisy measurements A1.t. the constrained optimization requires that the synthetic data D, satisfies y-accuracy with respect the noisy measurements for all the selected queries in Q1:-- Then among the set of feasible distributions that satisfy accuracy constraints, PEP selects the distribution with maximum entropy, leading to the following regularized constraint optimization problem:
minimize:
Σ
D(x) (D(x))
(5)
DEA
subject to: Vie
ā (D) S7,
D(x)==1 FEX
We can ignore the constraint that ExEx (x) 0, because will be satisfied automatically.
The solution of (5) is an exponentially weighted distribution parameterized by the dual variables A A corresponding to the i constraints. Therefore, if solve the dual problem of in terms of the dual variables A1...., A, then the distribution that minimizes (5) is given by (x X
exp | (1)) (Note that MWEM simply sets X; = ã - q. (D:-1) without any optimization.)
Given that the set of distributions is parameterized by the variables Ar..... r, the constrained optimization is then equivalent to minimizing the following exponential loss function:
Σ dr (T:(2) k.)) )) +1Alllaa
CEP (N, = loog
Σ NEE
cxp
Since PEP requires solving this constrained optimization problem on each round, we give an efficient iterative algorithm for solving (5). We defer the details of the algorithm the Appendix C
6 Extending to the public-data-assisted setting
Incorporating prior information from public data has shown to be promising avenue for private query release 66 26]. Therefore, we extend GEM to the problem of public-data-assian assisted private (PAP) query release o in which differentially private algorithms have access to public data. Concretely, we adapt GEM utilize public data by initializing D, to a distribution over the public dataset. However, because in GEM, we implicitly model any given distribution using a generator G, we must first train without privacy (i.e., without using the exponential and Gaussian mechanisms) generator Gpub to minimize the fieerror over some set of queries Q Note that in most cases, we can simply let Q Q= Q where Q is the collection of statistical queries we wish answer privately. GEMPub then initializes Go to Gpub and proceeds with the rest of the GEM algorithm.
6.1 Overcoming limitations of PMWPub
We describe the limitations of PMWPub by providing two example categories of public data that it fails to use effectively. We then describe how GEMPub overcomes such limitations in both scenarios.
Public data with insufficient support. We first discuss the case in which the public dataset has an insufficient support, which in this context means the support has high best-mixture-error 26 Given some support S C X, the best-mixture-erron can be defined as
min max q (D) Σ >= (29(2) (EA(S) VEQ
#ES
7

---

where j E A(S) is a distribution over the set S with p(z) 2 0 for all z E S and Exes u(x) = 1.
In other words, the best-mixture-error approximates the lowest possible max error that can be achieved by reweighting some support, which in this case means PMWPub cannot achieve max errors lower that this value. While Liu et al. [26] offer a solution for filtering out poor public datasets ahead of time using small portion of the privacy budget, PMWPub cannot be run effectively if no other suitable public datasets exist. GEMPub however avoids this issue altogether because unlike MWEM (and therefore PMWFub), which cannot be run without restricting the size of DD, PEM can utilize public data without restricting the distributional family can represent (since both GEM and GEM Pub compactly parametrize any distribution using a neural network).
Public data with incomplete data domains. Next we consider the case in which the public dataset only has data for subset of the attributes found in the private dataset. We note that presented in Liu et al. [26), PMWPub cannot handle this scenario. One possible solution to augment the public data distribution by assuming uniform distribution over all remaining attributes missing in the public dataset. However, while this option may work in cases where only a few attributes are missing, the missing support grows exponentially in the dimension of the missing attributes. In contrast, GEMPub Pub can still make use of such public data. In particular, we can pretrain a generator G on queries over just the attributes found in the public dataset. Again, GEMPub avoids the computational intractability of PMWPub in this setting since it parametrizes its output distribution with G.
7 Empirical Evaluation
In this section, we empirically evaluate GEM and PEP against baseline methods on the ACS 34 and ADULT K datasets in both the standard and public-data-asiitted settings.
Data. To evaluate our methods, we construct public and private datasets from the ACS and ADULT datasets by following the preprocessing steps outlined in Liu et al. (26). For the ACS, we use 2018 data for the state of Pennsylvania (PA-18) 18) as the private dataset. For the public dataset, we select 2010 data for Pennsylvania (PA-10) and 2018 data for California (CA-18). In experiments on the ADULT dataset, private and public datasets are sampled from the complete dataset (using a 90-10 split). In addition, we construct oow-dimeniional versions of both datasets, which we denote as ACS (reduced) and ADULT (reduced), in order to evaluate PEP and MWEM.
Baselines. We compare our algorithms to the strongest performing baselines in both low and high- dimensional settings, presenting results for MWEM, DualQuery, and RApsoltmax in the standard setting and PMWPub in the public-data-sssisteed setting.
Experimental details. To present a fair comparison, we implement all algorithms using the privacy mechanisms and zCDP composition described in Section 3.1 To implement GEM for k-way marginals, we select a simple multilayer perceptron for Gg. Our implementations of MWEM and PMWPub output the last iterate D, instead of the average and apply the multiplicative weights update rule using past queries according to the pseudocode described in Liu et al. (26 We report the best performing 5-run average across hyperparameter choices (see Tables D.I for each algorithm.
and
Appendix
7.1 Results
Standard setting. In Figure we observe that in low-dimensional settings, PEP and GEM con- sistently achieve strong performance compared to the baseline methods. While MWEM and PEP are similar in nature, PEP outperforms MWEM on both datasets across all privacy budgets except
3 We refer readers to Appendix D.7 where we include an empirical evaluation on versions of the ADULT and
LOANS [ datasets used in other related private query release works 28 40 5.
Having consulted McKenna et al. (28), we concluded that running HDMM is infeasible for our experiments,
since it generally cannot handle data domain with size larger than 10 See Appendix D.5 for more details.
'Because RAP performs poorly relative the other methods in our experiments, plotting its performance would make visually comparing the other methods difficult. Thus, we exclude it from Figure and refer readers Appendix D.3 where present failure cases for RAP and compare it to Ra
8

---

ACS (red.) PA-18
ADULT (red.)
ACS PA-15
ADULT
0.08
0.20
0.20
Max Error
0.06-
0.10
0.15
0.15
0.04
0.10
0.10
0.05
0.05
0.05
0.00
0.135
0.25
0.5
1.0
0.125
0.25
0.125
0.25
0.5
0.125
0.25
1.0
Privacy Budget
GEM
RAPMin
DualQuery
PEP
MWEM
Figure I: Max error for 3-way marginals evaluated on ADULT and ACS PA-18 using privacy budgets E {0.1, 0.15, 0.2, 0.25, 0.5, }} and 6 = π.. The x-axis uses logarithmic scale. We evaluate using the following workload sizes: ACS (reduced) PA-18: 455; ADULT (reduced): 35; ACS PA-18: 4096; ADULT: 286. Results are averaged over 5 runs, and error bars represent one standard error.
PA-18 / CA-18
PA-18 PA-10
GEM
0.10
GEMPA
0.06
GEMPa (red.)
Max Error
0.08
Max Error
0.05
0.06
0.04
0.04
0.03
0.02
0.02
0.125
0.25
0.5
0.125
0.25
0.01
Privacy Budget (E)
0.125
0.25
10
GEM
GEMPL
PMW
Privacy Budget (e)
(a) ACS PA-18
(b) ADULT
Figure 2: Max error for 3-way marginals with privacy budgets E (0.1, 0.15, 0.2, 0.25, 0.5, 1] and
n,2- The x-axis uses logarithmic scale. Results are averaged over runs, and error bars represent algorithms with the following public datasets: Left: 2018 California (CA-18); Right: 2010 Pennsylvania (PA-10), 10). (b) ADULT (workloads = 286). We evaluate GEM using both the complete public data (GEMPub) and reduced version that has fewer attributes (GEMPub (reduced)).
5 1 one standard error. (a) ACS PA-18 (workloads 4096). We evaluate ioolic-data-sssisee
E (0.1,0.15) on ACS (reduced), where the two algorithms perform similarly. In addition, both PEP and GEM outperform RApsofimax Moving to the more realistic setting in which the data dimension is high, we again observe that GEM outperforms RApsoflmax on both datasets.
Public-data-assisted setting. To evaluate the query release algorithm in the public-data-assisted setting, we present the three following categories of public data:
Public data with sufficient support. To evaluate our methods when the public dataset for ACS PA-18 has low best-mixture-erae GEMPub performs similarly to PMWPub with both outperforming GEM (without public data).
consider the public dataset ACS PA-10. We observe in Figure that
Public data with insufficient support. In Figure 2b, we present CA-18 as example of this failure is over 10%, and so for any privacy budget, PMWPub cannot achieve emrrr lower that this value. However, for the reasons described in Section 6.1 GEMPub not restricted by best-mixture-erro and significantly outperforms GEM (without public data) when using either public dataset.
case in which the best-mixture-enn
Public data with incomplete data domains. To simulate this setting, we construct reduced version of the public dataset in which we keep only 7 out of 13 attributes in ADULT. In this case, 6 attributes are missing, and so assuming a uniform distribution over the missing attributes would cause the dimension of the approximating distribution D to grow from ~ 4.4 x 10 to R 3.2 x 10 PMWPub would be computationally infeasible to run in this case. To evaluate GEMPub we pretrain the generator G using all 3-way marginals both the complete and reduced versions of the public

---

dataset and then finetune on the private dataset (we denote these two finetuned networks as GEM and GEMPub (reduced) respectively). We present results in Figure 2p. Given that the public and private datasets are sampled from the same distribution, GEMPub unsurprisingly performs extremely well. However, despite only being pretrained on a small fraction of all 3-way marginal queries ( 20k out 334k), GEMPub (reduced) is still able to improve upon the performance of GEM and achieve lower max error for all privacy budgets.
Conclusion
In this work, we present framework that unifies long line of iterative private query release algo- rithms by reducing each method to a choice of some distributional family DD and loss function L. We then develop two new algorithms. PEP and GEM, that outperform existing query release algorithms. In particular, we empirically validate that GEM performs very strongly in high dimensional settings (both with and without public data). We note that we chose rather simple neural network architecture for GEM, and so for future work, we hope to develop architectures more tailored to our problem. Furthermore, we hope to extend our algorithms other query classes, including mixed query classes and convex minimization problems 377
Limitations. While our empirical study is structured based on past work in the literature, real- world deployment of differential privacy may be more nuanced. For example, though GEM achieves strong performance on the ACS dataset in our experiments, we (and possibly the U.S. Census Bureau itself) do not know yet what the end goals of differentially private ACS release should be. Given different constraints or evaluation metrics,
possible for another technique be more suitable.
Broader impacts. We note that a possible consequence of privacy preserving methods is their potential to bring about unfair outcomes. Fioretto et al. [8], for example, show that decisions based on DP analyses may disproportionately impact certain groups. Because the U.S. Census Bureau has plans adopt differential privacy for ACS releases after 2025 [23), the ACS dataset serves the main test bed for our algorithms. We believe it is important to ensure that fairness is preserved for downstream tasks that use DP synthetic dataset, since the ACS provides statistics that are critical to many important decision processes (e.g., Title I grant allocations
Acknowledgments
ZSW is supported by NSF grant SCC- 1952085, Carnegie Mellon CyLab's Secure and Private IoT Initiative, and Google Faculty Research Award.
References
[1] Small area income and poverty estimates (saipe) program: Faqs. http://https:// //Ww census. http://pogramm-suurrrrrss/aapppp
html
[2] Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp. Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jazefowiez, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng, TensorFlow: Large- scale machine learning on heterogeneous systems, 2015. URL Www.httpss:. /tttpss:/www... http:::::/wwwwwttsfllllllom org/ Software available from tensorflow.org.
[3] John M. Abowd. The U.S. census bureau adopts differential privacy. In ACM International Conference Knowledge Discovery & Duta Mining, page 2867, 2018.
[4] Noga Alon, Raef Bassily, and Shay Moran. Limits of private learning with access to public data. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neurul Information Processing Systems, volume 32. Cur- ran Associates, Inc., 2019. URL httptttppe/ppcceiinnggeeeeeeee/e nwwrinu catssecc/pcce cc/ppappr//2/9/ffleee 2af211aaaee773555227777888888883
Paper pdf
10

---

[5] Sergul Aydore, William Brown, Michael Kearns, Krishnaram Kenthapadi, Luca Melis, Aaron Roth, and Ankit Siva. Differentially private query release through adaptive projection. arXiv preprini arXiv:2103.0mm
2021.
[6] Raef Bassily, Albert Cheu, Shay Moran, Aleksandar Nikolov, Jonathan R. Ullman, and Zhi- wei Steven Wu. Private query release assisted by public data. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 695-703. PMLR, 2020. URL http://procceeding.. mlr. wwwss/ 19/119////aa htt.///aasellyl..aaaaaaa html
[7] Raef Bassily, Shay Moran, and Anupama Nandi. Learning from mixtures of private and public populations. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tiee Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. URL http::://ppocceeec p/ttceed//rrocedingg neur wttppppp.cpppppp/p/.eeeeee 22////2220/haaa (ee942c6b18200f 041
www.tbastttttoo. html
[8] Brett K Deeuliiu-Jonnss Zhiwei Steven Wu, Chris Williams, Ran Lee, Sanjeev P Bhavnani, James Brian Byrd, and Casey Greene. srivacyprreeeving generative deep neural networks support clinical data sharing. Circulation: Cardiovascular Quality and Outcomes, 12(7):
e005122, 2019.
[9] Avrim Blum, Katrina Ligett, and Aaron Roth. A learning theory approach to non-interactive database privacy. In Cynthia Dwork, editor, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 609-618. wwg///.///./ 1145/337377/
ACM, 2008. doi: 10. 10.1145/13744376.3344666
1374464
[10] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Proceedings of the 14th Conference on Theory of Cryptography, TCC 16-B, pages 635-658, Berlin, Heidelberg, 2016. Springer.
[11] Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approxi- mate differential privacy, SIAM Journal on Computing, 47(5):1888-1938 2018.
[12] Mark Cesar and Ryan Rogers. Unifying privacy loss composition for data analytics. arXiv preprint WxXiv:2004.072233 2020.
[13] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL Utthttpp//arcchiv
ics.uci. wwci.edul edu/mm ml
[14]
Cynthia Dwork and Guy N. Rothblum. Concentrated differential privacy, 2016.
[15] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensi- tivity in private data analysis. In Proceedings of the 3rd Conference on Theory of Cryptography, TCC '06, pages 265-284 265-284, Berlin, Heidelberg, 2006. Springer.
[16) Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil Vadhan. On the complexity of differentially private data release: Efficient algorithms and hardness re- sults. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC '09, page 38 1390,, New York, NY, USA, 2009, Association for Computing Machinery. doi: 10. 1536414. 1536467
ISBN 978 178160555006..
URL https://doi. becoooi.org//// 1ttp//1.11555
[17] Alexander Edmonds, Aleksandar Nikolov, and Jonathan Ullman. The power of factorization mechanisms in local and central differential privacy. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020. page 425-438, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 978 15936699997 doi: 10. 10.1145/3357713.
3384297. URL wttph:ttt:/tt... /tttts:/s//.........ttttt org/ 111111...11111 1145 3384297
[18] Ferdinando Fioretto, Cuong Tran, and Pascal Van Hentenryck. Decision making with differential privacy under fairness lens. arXiv preprint arXiv:2105.07511 2021.
[19] Marco Gaboardi, Emilio Jesús Gallego Arias, Justin Hsu, Aaron Roth, and Zhiwei Steven Wu. Dual query: Practical private query release for high dimensional data. In International Conference on Machine Learning, pages 1170-1178. PMLR, 2014.
[20] Anupam Gupta, Aaron Roth, and Jonathan Ullman. Iterative constructions and private data release In Proceedings of the 9th International Conference Theory of Cryptography, TCC' 12,

---

page 339-356, Berlin, Heidelberg. 2012. Springer-Verlag ISBN 978364228912.. doi: 10. 1001/ 178-3-642-289144 19.
2942228914-9111
[21] Moritz Hardt and Guy N Rothblum. multiplicaative weights mechanism for privacy- preservin data analysis. In 2010 IEEE 51 Anmual Symposium on Foundations of Computer Science, pages 61-70. IEEE, 2010.
[22] Moritz Hardt, Katrina Ligett, and Frank Mesherry. A simple and practical algorithm for differentially private data release. In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 25. Cur- ran Associates, Inc., 2012.
pdf
[23] Ron Jarmin. Census bureau continues boost data safeguards, U.S. Census: Random Samplings Blog. URL httphhtpp///wwtt census. wwensss.gov/nesssroomoooo wwwpg///wwwrroooooogg///aaaaaaae http://wooaaaaaooaaooooaaaaaaaaa
boost- moost-safeguarde.hmg html
[24] Daniel Kifer. Consistency with external knowledge: The topdown algorithm, 2019, http:
/
[25] Chao Li, Gerome Miklau, Michael Hay, Andrew Megregor, and Vibhor Rastogi. The matrix mechanism: Optimizing linear counting queries under differential privacy. The VLDB Journal, 24(6)7557771,, December 2015. ISSN 1066-8888.
doi: 10. 10.1007/00078--055--39-- URL
htt.://rrr//...00000000000000000 https://doi.orr 1007 00000//00778-00--038-8--01
[26] Terrance Liu, Giuseppe Vietri, Thomas Steinke, Jonathan Ullman, and Zhiwei Steven Wu. Leveraging public data for practical private query release. arXiv preprint arXiv:2102.08598, 2021.
[27] Andre Martins and Ramon Astudillo. From softmax to sparsemax: A sparse model of attention and multi-label classification. In International conference on machine learning, pages 1614 1623. PMLR, 2016.
[28] Ryan McKenna, Gerome Miklau, Michael Hay, and Ashwin Machanavaijhala. Optimizing error of high-dimensional statistical queries under differential privacy. Proc. VLDB Endow., 11(10):100-1219, June 2018. ISSN 2150-8097.
doi: 101447883231751..331666 URL
https://doi. org/10...... 01778/3231151111 3231769
[29] Ryan McKenna, Daniel Sheldon, and Gerome Miklau, Graphical-mode based estimation and inference for differential privacy. In International Conference on Machine Learning, pages 4435-4444. PMLR, 2019.
[30] Marcel Neunhoeffer, Steven Wu, and Cynthia Dwork. Private post-[gan] boosting. In Inter- national Conference Learning Representations, 2021. URL https::/ net/
forum?id=6isffRJIch
[31] Aleksandar Nikolov, Kunal Talwar, and Li Zhang. The geometry differential privacy: The sparse and approximate cases. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC '13, page 351-360, New York, NY, USA, 2013. Association for Computing Machinery. ISBN 978 7781450320290. doi: 10. 10.1145/2488608, 24884488800..28885222 URL
10210..145/// 1141 2484588 2488652
[32] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style. high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024-8035. 8035. Curran Associates, Inc., 2019. httptttp://ppprrrr http://pppprrooorrrisssspppapppp cc/paper/ -ibbrrr
pdf
[33] Aaron Roth and Tim Roughgarden. Interactive privacy via the median mechanism. Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA. 5-8 June 2010, pages 765-774. ACM, 2010. doi: 10.1 0t55//8806691118077999 URL //op:::/doo.. org/org///1 1145/18066660 118188
[34] S Ruggles al. lpums usa: Version 10.0, doi: 10./0100/ VI0. 0, 2020.
12

---

[35] Robert E Schapire and Yoar Freund. Boosting; Foundations and algorithms. Kybernetes, 2013.
[36] Jonathan Ullman. Answering n<sub>2+00 / counting queries with differential privacy hard. In Proceedings of the Forty-Fisth Annual ACM Symposium Theory of Computing, STOC 13, page 361-370, New York, NY, USA, 2013. Association for Computing Machinery. ISBN 9781 7781450320290. doi: 10.1 10.1145//488608. 2488653. URL https://ddi. becooi..rgg/11 org/10....... 1145/ 2488608 2488653
[37] Jonathan Ullman. Private multiplicative weights beyond linear queries. Proceedings of the 34th ACM
Symposium Principles of Database Systems, PODS '15, page 303-312, New York, NY, USA, 2015. Association for Computing Machinery, ISBN 9781450327572. doi: 00.11455274555547445555 URL htthh:htts::ooo... http://too.orr////// 1145/ 2745754. 2745755
[38] Jonathan Ullman and Salil Vadhan. Peps and the hardness of generating private synthetic data.
In Theory of Cryptography Conference, pages 400-416, Springer, 2011.
[39] Jonathan Ullman and Salil Vadhan. Peps and the hardness of generating private synthetic data. In Yuval Ishai, editor, Theory of Cryptography, pages 400-416, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. ISBN 978-3-642-19571
[40] Giuseppe Vietri, Grace Tian, Mark Bun, Thomas Steinke, and Steven Wu. New oracle-efficient algorithms for private synthetic data release. In International Conference on Machine Learning, pages 9765-9774. PMLR, 2020.
[41] Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforce- ment learning. Machine learning, 8(3):229-25) 256, 1992.
[42] Liyang Xie, Kaixiang Lin, Shu Wang, Fei Wang, and Jiayu Zhou. Differentially private generative adversarial network. CoRR, abs/1802.06739, 2018. URL http://arxiv.. org/
abs/1802. 06739
[43] Yasin YaZIcı, Chuan-Sheng Foo, Stefan Winkler, Kim-Hui Yap, Georgios Piliouras, and Vi- jay Chandrasekhar. The unusual effectiveness of averaging in gan training. arXiv preprint arXiv:1806.044 04498, 2018.
[44] Jinsung Yoon, James Jordon, and Mihaela van der Schaar. PATE-GAN: Generating synthetic data with differential privacy guarantees. In International Conference Learning Representa- tions, 2019. httpshtts::/// httt:p///ppparrrreeeeee//r/r//rs
13


Reviews:
[{"review_id": "u3Jjo7khq6_", "reviewer": "Reviewer_ZboG", "summary": "# Summary of contributions\n\nThe 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].\n\nThe 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).\n\nWith 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.\n\nThe 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.\n\nFinally, 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.", "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": "# Evaluation\n\n## Strengths\n\n- 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.\n\n## Weaknesses\n\n- 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.)\n- 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.)\n- 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.\n\n## Recommendation\n\nOverall, 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.\n\n# Detailed Comments\n\n- **Issues with PEP Algorithm**:\n  - 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?\n  - 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.\n  - 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.\n- **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.\n\nMinor comments:\n- **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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5"}, "extra_text": {}}, {"review_id": "_vmVIMHPukj", "reviewer": "Reviewer_aLmv", "summary": "The paper has two main contributions:\n\n1) 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.\n\n2) 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.", "questions": "", "limitations": "", "rating": 7, "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": "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.\n\n2) 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?\n\n3) 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?\n  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, both the limitations and societal impact have been addressed adequately.", "review_text": "", "extra_scores": {"ethical_concerns": "Not applicable.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "M5i6-r6geC", "reviewer": "Reviewer_Tcj3", "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.\n", "questions": "", "limitations": "", "rating": 8, "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": "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. \n\nMinor issues:\nLine 91, typo. “Lete” \nLine 149: “where describe” -> where we describe ?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "The authors mention that DP can cause unfair outcomes for certain groups, the Census Bureau example is discussed.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "0JHpW4cmnFP", "reviewer": "Reviewer_cnAp", "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. \n\nGiven 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. \n\nEmpirically, 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.\n", "questions": "", "limitations": "", "rating": 7, "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": "Originality / Significance:\nThis 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.\n\nQuality:\nThe 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). \n\nClarity:\nAs 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.\n\nFor 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. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately note their limitations and possible ethical concerns (i.e known issues of DP and fairness). ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}]

Author rebuttal:

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)