Private Synthetic Data for Multitask Learning and Marginal Queries
Authors: Giuseppe Vietri
Cedric Archambeau
Sergul Aydore
William Brown
Michael Kearns
Aaron Roth
Ankit Siva
Shuai Tang
Steven Wu
Venue: NeurIPS 2022 Accept (2022)

Abstract: We provide a differentially private algorithm for producing  synthetic data simultaneously useful for multiple tasks: marginal queries and multitask machine learning (ML). A key innovation in our algorithm is the ability to directly handle numerical features, in contrast to a number of related prior approaches which require numerical features to be first converted into {high cardinality} categorical features via {a binning strategy}. Higher binning granularity is required for better accuracy, but this negatively impacts scalability. Eliminating the need for binning allows us to produce synthetic data preserving large numbers of statistical queries such as marginals on numerical features, and class conditional linear threshold queries. Preserving the latter means that the fraction of points of each class label above a particular half-space is roughly the same in both the real and synthetic data. This is the property that is needed to train a linear classifier in a multitask setting. Our algorithm also allows us to produce high quality synthetic data for mixed marginal queries, that combine both categorical  and numerical features. Our method consistently runs 2-5x faster than the best comparable techniques, and provides significant accuracy improvements in both marginal queries and linear prediction tasks for mixed-type datasets.  

Private Synthetic Data for Multitask Learning and Marginal Queries
Giuseppe Vietri University of Minnesota vietr0020umn edu
Cedric Archambeau
Sergul Aydore Amazon AWS AI/ML saydore@amazon com
Amazon AWS AI/ML
cedrica@amazon com
William Brown Columbia University w. broonncolumbia edu
Michael Kearns Amazon AWS AI/ML University of Pennsylvanie mkearns@cis upenn edu
Aaron Roth Amazon AWS AI/ML University of Pennsylvania aaroth@cis upenn edu
Ankit Siva
Shuai Tang Amaoon AWS AI/II
Zhiwei Steven Wu Amazon AWS AI/MI Carnegie Mellon University zhiveiw@andrew. cmu edu
Amazon AWS AI/MI
ankitsivdamazon.c com
shuat@amazon.comm com
Abstract
We provide differentially private algorithm for producing synthetic data simulta- neously useful for multiple tasks: marginal queries and multitask machine learning (ML). A key innovation in our algorithm is the ability directly handle numer- ical features, in contrast to a number of related prior approaches which require numerical features be first converted into high cardinality categorical features via binning strategy. Higher binning granularity is required for better accuracy, but this negatively impacts scalability. Eliminating the need for binning allows to produce synthetic data preserving large numbers of statistical queries such as marginals on numerical features, and class conditional linear threshold queries. Preserving the latter means that the fraction of points of cach class label above a particular half-space roughly the same both the real and synthetic data. This is the property that is needed to train a linear classifier in a multitask setting. Our algorithm also allows us to produce high quality synthetic data for mixed marginal queries, that combine both categorical and numerical features. Our method consis- tently runs 2-5x faster than the best comparable techniques, and provides significant accuracy improvements in both marginal queries and linear prediction tasks for mixed-type datasets.
Introduction
We study the problem of synthetic data generation subject the formal requirement of differential privacy [DMNS06]. Private synthetic data have the advantage that they can be reused without any further privacy cost. As a result, they can use limited privacy budget simultaneously enable wide variety of downstream machine learning and query release tasks.
Giuseppe is the lead author; all other authors are listed in alphabetical order. Giuseppe performed this work during an internship AWS AI/MI William performed this work during an internship at AWS AI/M...
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Recent work on practical methods for private synthetic data has largely split into two categories. The first category builds on the empirical success of deep generative models and develops the correspond- ing private implementations, such as DP-GAN (XLW+18 18 BJWW+19
NWD220 [YvdS18]. The second category follows the principle of moment-matching and generates synthetic data that preserve a large family of marginal queries [[LMM12 GAH+ 14, MSM19 MPSM2T, ABK* MMSM22 LVW21]. For both downstream machine learning and query release tasks, the moment-matchinn approach has generally outperformed private deep generative models TMH++11, which are known to be difficult to optimize subject to differential privacy (NWD20) In order to handle numerical features, they are discretized into finite number of categorical bins. This binning heuristic is impractical for real-world datasets, which often contain a large number numerical features with wide ranges.
Our work develops a scalable, differentially private synthetic data algorithm, called RAP++, that builds on the previous framework of "Relaxed Adaptive Projection" " (RAP) TABK+21 but can handle mixture of categorical and numerical features without any discretization. As with RAP, the core algorithmic task of RAP++ to use differentiable optimization methods (e.g. SGD or Adam) to find synthetic data that most closely matches a noisy set of query measurements on the original data. We introduce new techniques to be able to do this for queries defined over a mixture of categorical and numerical features. Two key components that drive the success of our approach includes (+) random linear projection queries to handle mixed-type data, and (+) tempered sigmoid annealing on top of the existing work RAP. Hence, we refer to our algorithm as RAP++. Our contributions can be summarized as follows:
Mixed-type queries. To capture the statistical relationships of a mixture of categorical and numerical features, we consider two classes of statistical queries on continuous data that previous work can only handle through binning of real values into high cardinality categorical features. The first class of queries we consider is mixed marginals, which capture the marginal distributions over subsets of features. Second, we define the class of class-conditional linear threshold functions, which captures how accurate any linear classifier is for predicting a target label (which can be any one of the categorical features). Therefore, we can generate synthetic data for multitask learning by choosing a suitable set of conditiond queries. where the conditioning is on multiple label columns of the data. The inability of previous work to handle mixed-type data without binning has been acknowledged as an important problem MMSM22], and our approach takes a significant step towards solving it.
Tempered sigmoid annealing. Since both classes of mixed-type queries involve threshold functions that are not differentiable, we introduce sigmoid approximation in order to apply the differentiable optimization technique in RAP. The sigmoid approximation is smooth approximation to a threshold function of the form T+cxp(-o(xx-6)) 6]]= where a is called the inverse temperature parameter controlling
the slope of the function near the threshold b. However, choosing the right parameter a involves a delicate trade-off between approximation and optimization. To balance such trade-off's, we provide an adaptive gradient- based optimization method that dynamically increases the inverse temperature a based on the gradient norms of iterates. We show that our method can still reliably optimize the moment- matching error even when no fixed value of can ensure both faithful approximation and non-vanishing gradient.
Empirical evaluations. We provide comprehensive empirical evaluations comparing RAP++ against several benchmarks, including PGM [MSM19, DP-CTGAN [DK22), and DP-MERF НAP21 on datasets derived from the US Census. In terms of accuracy, RAP++ outperforms these benchmark methods in preserving the answers for the two classes of mixed-type queries. We also train linear models for multiple classification tasks using the synthetic datasets generated from different algo- rithms. We find that RAP++ provides the highest accuracy when the numeric features are predictive of the target label, and closely tracks all benchmark accuracy in all other cases.
2 Preliminaries
We use X' = 2i x... x X's to denote a d-dimensional data domain, where i-th feature has domain X, For a set S of features, we denote the projected domain onto S as X's = Il X, This work assumes that each feature domain X; can be either categorical or continuous. If a feature i is categorical, it follows that X; is finite unordered set with cardinality |.&.] and if it is continuous then X, = IR. A datasct De E X² is multiset of points of arbitrary size from the domain. For any point E X, we
2

---

use 2j E X; to denote the value of the i-th feature and for any set of features S, let rs = (Ii)sss be the projection of E X onto Xz.. The algorithm in this work is based on privately releasing statistical queries, which are formally defined here.
Definition 1 (Statistical Queries [Kea98]) statistical query (also known as a linear query or counting query) is defined by a function q X + [0, 1]. Given a dataset D, we denote the average value of q on D as: (DD D EEED
2.1
Mixed-type Data and Threshold Queries
In this section we consider multiple classes of statistical queries of interest. Most previous work on private synthetic data generation focuses on categorical data and in particular preserving marginal queries, which are formally defined as follows:
Definition 2 (Categorical Marginal queries ). A k-way marginal query is defined by set of categori- cal features of cardinality |S] = k, together with a particular element e E Ilies X; in the domain of S. Given such a pair (S, let X(S, c) = {I X .g = =c} denote the set of points that match The corresponding statistical query q8,c is defined as qs,e(I) = 11x E X(S, c)}, where 1 is the indicator function.
Prior work on private query release BL RO8
GAH+14 MSM19 ABK 21 MMSM22 VTB+ 20
GAH+14 [VW21] considered only categorical marginal queries and handled mixed-type data by binning numerical features. This work considers query classes that model relations between categorical and numerical features, which we call Mixed Marginals, without needing discretize the data first. One example of a Mixed Marginal query is: "the number of people with college degrees and income at most $50K". This example is mixeed-arginal because it references a categorical feature (i.e., education) and numerical feature (i.e., income).
Definition 3 (Mixed Marginal Queries). A k-way mixed-marginal query is defined by a set of categorical features C, an element y E Xc, a set of numerical features R and a set of thresholds т. with |C| + R = k and [R| [T.. Let XC,, y) be as in definition 2 and let (RR r) {a e X 2j S. T3 Y (ER denote the set of points where each feature E R. R.fall below its corresponding threshold value Tj. Then the statistical query 9C,y, R.r defined as
(C.,,,,(x)) 1a E (CC, 1fx E (RR
Another natural query class that we can define continuous valued data is linear threshold query which counts the number of points that lie above halfspace defined over the numeric features. A class conditional linear threshold query is defined by a target feature i, and counts the number of points that lie above a halfspace that take a particular value of feature i.
Definition 4 (Class Conditional Linear Threshold Query). A class conditional linear threshold query is defined by categorical feature i, target value E X, a set of numerical features R, vector 0 E 18 Rl and a threshold
as R. (z) 1 (0 HR) S and x; = y).
The quality of synthetic data can be evaluated in task specifs ways. Since the goal is to accurately answer set of queries over numerical features, we can evaluate the difference between answers to the queries on the synthetic data and those on the real data, summarized by an l norm. Definition 5 (Query Error). Given set of statistical queries Q {qI..... }m the average error of a synthetic dataset Đ is given by: 1 E (D: - q: (D)). m
2.2 Differential Privacy
The notion of privacy that we adopt in this paper is differential privacy, which measures the effect of small changes in a dataset on randomized algorithm. Formally, we say that two datasets neighboring if they are different in at most one data point.
Definition 6 (Differential Privacy (DNN061). ). A randomized algorithm M 2m R. satisfies
(e, didfifffellt privacy if for all neighboring datasets D, D' and for all outcomes S C R. we have
Pr Pr(M(D) E S] < e Pr E S)+ 5
In our analysis we adopt a variant of DP known as (zero) Concentrated Differential Privacy which more tightly tracks composition and can be used to bound the differential privacy parameters and 8:
3

---

Definition 7 (Zero Concentrated Differential Privacy BSI6aa ). A randomized algorithm M : X R satisfies p-zero Concentrated Differential Privacy (p-2CDP) for all neighboring datasets D, D', and for all a E (0, o)): TD gence between the distributions M(D) and M(D').
S po, where DD (M(D), is a-Renyi diver-
We use two basic DP mechanisms that provide the basic functionality of selecting high information queries and estimating their answers. To answer statistical queries privately, mechanism, which we define in the context of statistical queries:
the Gaussian
Definition 8 (Gaussian Mechanism). The Gaussian mechanism G q: p) takes as input dataset
D E X², statistical query X + [0, 1}, and a zCDP parameter It outputs noisy answer â= (D) + Z, where Z NO, 2m.p). where the number of rows in D.
Lemma (Gaussian Mechanism Privacy [BS ). For any statistical query q, and parameter > the Gaussian mechanism (.). satisfies p-zCDP.
Answering all possible queries from large may be expensive in terms of privacy, the noise added to each query scales polynomially with the number of queries. A useful technique from GHRUM is to iteratively construct synthetic data by repeatedly selecting queries on which the synthetic data currently represents poorly, answering those queries with the Gaussian mechanism, and then re-constituting the synthetic data. Thus, we need private selection mechanism. We use the Report Noisy Top- K mechanism [RI9, defined here in context of selecting statistical queries.
Definition 9 (One-shot Report Noisy Top-K With Gumbel Noise). The "Report Noisy Top-K" S.Q),, D,Q,
mechanism RNK (D, (DDDD,,
takes as input a dataset D E X" with n rows, a "synthetic dataset"
δ E X", a set of m statistical queries Q Q= == Jm.. and zCDP parameter First, it adds Gumbel noise to the error of each qi E Q:
0. = ( (D) + Zr where Zi ~ Gumbel (K/ 22m))
Let i(1),..., (()) be an ordered set of indices such that Diay 2,... Diimy The algorithm oulputs the top-K K indices {iça)....,((3) corresponding to the K queries where the answers between D and i differ most.
Lemma (Report Noisy Top-K Privacy ABK ABK+ For a dataset D, a synthetic dataset D, a set of statistical queries Q, and 2CDP parameter p. (D, D, Q,p) satisfies p-zCDP.
3 Relaxed Projection with Threshold Queries
In this section we propose gradient-based optimization routine for learning a mixed-type synthetic datasets that approximate answers to threshold based queries over continuous data. The technique is an extension of the relaxed projection mechanism from [ABK A21++11, which in turn extends the projection mechanism of [NTZ13]
Given a dataset D, a collection of m statistical queries Q = {9....., Im and zCDP parameter the projection mechanism [NTZ consists of two steps: (1) For each query index E [m], evaluate on D using the Gaussian mechanism: à; G(D, qs p/m m). and then (2) Find synthetic dataset D' e X whose query values minimize the distance the noisy answers (a))e))))
arg min Eie(m) (a, (a.-q. (D'))
The projection step produces synthetic data that implicitly encodes the answers to all queries in the query set Q. addition to producing synthetic data (which can be used for downstream tasks like machine learning which cannot casily be accomplished with the raw outputs of the Gaussian mechanism), by producing a synthetic dataset, the projection step by definition enforces consistency constraints across all query answers, which is accuracy improving. Unfortunately, the projection step is generally an intractable computation since it a minimization of a non-convex and non-differentiable objective over an exponentially large discrete space. To address this problem, [ABK gives an algorithm that relaxes the space of datasets X to a continuous space, and generalizes the statistical queries to be differentiable over this space:
Domain relaxation. The first step is to represent categorical features as binary features using one-hot encoding. Let d' := Eiec (a), where C' is the set of categorical features, be the dimension of the

---

feature vector under the one-hot encoding. Then, we consider a continuous relaxation denoted by X of the one-hot encoding feature space. Using ((X) to denote probability space over the elements of R, we choose X' == Ie ((X)) to be the product measure over probability distributions over the one-hot encodings. The advantage of representing the relaxed domain probability space is that one can quickly recover a dataset in the original discrete domain by random sampling.
Differentiable queries. The next step is to replace the set of queries Q by set of continuous and differentiable queries Q over the relaxed domain X. Informally, in order to solve our optimization problem, the queries must be differentiable over the relaxed domain X' (and have informative gradients), but must also be a good approximation to the original queries in Q so that optimizing for the values of the relaxed queries produces synthetic dataset that is representative of the original queries. For categorical marginal queries following [ABK+21], we use the set of product queries over the relaxed domain which are equal to categorical marginal queries the original domain:
Definition 10. Given subset of features T S [d"] of the relaxed domain X, the product query qr : X is defined as (2) = Iher Tzz
Next we give a differentiable relaxation for any class of threshold based statistical queries such as those in definition _ and definition 4 A linear threshold query is threshold applied to a linear function of the data, which is not differentiable. We choose to approximate thresholds with sigmoid functions. They are simple parametric class of functions with well-behaved gradients with adjustable magnitudes for the approximation error via the inverse temperature parameter:
Definition 11 (Tempered Sigmoid). The sigmoid threshold function f
R - [0, 1] with threshold
E R and inverse temperature > 0 is defined (x)) Itee ol= for any E RR
The sigmoid funetion in definition M is differentiable approximation of the class of 1-way prefix marginal queries, which serves as a basic building block for approximating other interesting classes of threshold-based queries, such as the class of conditional linear threshold queries.
Definition 12 (Tempered Sigmoid Class Conditional Linear Threshold Queries). A sigmoid con- ditional linear threshold query is defined by categorical feature i E [d"] of the relaxed domain space, set of numerical features T C [d') in the relaxed domain space, vector O R R[],, and threshold t E R.. Fixing the sigmoid temperature a, let f!o) be defined as in definition corresponding differentiuble statistical query is V.,T.e, (1) = xz; (10, xT))
11 then the
By relaxing the data domain to its continuous representation X and replacing the query set Q =
{gr.... } by its differentiable counterpart Q = (ū),-.. Im we obtain the new objective: arg mig.
D'ER. T((D"= = Eie(m) (ā: ax())))²
(2)
Since the new objective is differentiable everywhere in X we can run any first-order continuous opti- mization method to attempt to solve Q Were qa
Tyoe Max
Type m Moan
10a
good approximation for qi everywhere in X for all queries E [m]. then the solution to eq. would approximate the solution to eq. 4T. How- ever, there are two other challenges that arise when use the sigmoid approximation: flat gradients and near-threshold approximation quality. If the sig- moid function has a large o (inverse temperature), its derivatives at points far from the threshold have small magnitudes. In other words, sigmoid approx- imations to linear threshold functions have nearly flat gradients far from the threshold. In the flat gradi- ent regime, first order optimization algorithms fail because they get "stuck". This can be mitigated by using a small a.. But there is another issue: because threshold functions are discontinuous, any continu- ous approximation to threshold function must be
10
10
10
inverse temperatuue(c))
inverse temperttureeeee
Figure I: Comparison of the Maximum error (lcft) and the Mean error (right) of optimizing mixed marginals using our temperature annealing (red line) and using a fixed parameter (blue curve). It is clear that annealing the a parameter strategically during optimization leads lower error than using any fixed a parameter during the continuous pro- jection step. The error is over a set of 1000 random 2- way mixed-man -maginnal queries (see definition B. And the underlying dataset is described in detail section 5
5

---

Algorithm Relaxed Projection with Sigmoid Temperature Annealing
1: Input: set m sigmoid differentiable queries { Je set of target answers à (ashie(m)
initial inverse temperature 01 E R_, ,stopping condition y > O and initial dataset Dj.
2: for j =1 1 to J do
3: Set inverse temperature jj 01 -
4: Define the sigmoid differentiahle loss function: I,( =(D)=_EEne ( - a.) )
5: Starting with D + Dj. Run gradient descent L,( until [L, - 7, Set Dj+1 + D.
6: end for
7: Output Dj+1
Algorithm 2 Relaxed Adaptive Projection + Mixed Type Temperature Annealing (RAP++)
I: Input A dataset D with n records, a collection of m statistical queries Q fg)..... gm h. query samples per round K & m. number of adaptive epochs T S m/ K, the size of the synthetic dataset ét sigmoid temperature parameter and differential privacy parameters e, 6.
2: Let p by such that: = p + 2/ DVVplogg log((/8).
3: Initialize relaxed dataset D1 E Xn uniformly at random, and 01 E R."
4: for t= to T do
5: Choose K queries {g.,))e(()) C Q using RNx (D, De, Qr-1, +)
6: For each j E [K]. āz.j + g (D, Gt.i
7: Let Q: = (E(.,,EE and = (2rx)) )).
8: Let Q: be the set of differentiable queries corresponding to Qt
9: Project step: D441 +- Seeemoidd-eemppatture-e Anneaa-nnnnnnnnnnnna ā. Dr, 01,7).
10:
end for
Output: D7+1
poor approximation for points that are sufficiently close to the threshold. To make this poor approximation regime arbitrarily narrow, we would have to choose a large but this is in tension with the flat gradients problem mentioned earlier. As a result, not clear how to choose an optimal value for o.
We overcome this issue by using a 'temperature annealing" approach, described in detail in algo- rithm 11 Informally, we start with small a and run our optimization until the magnitude of the gradients of objective function fall below a pre-defined threshold. At that point, we double a and repeat, until convergence. The intuition behind this technique is that if the magnitude of the gradients has become small, we must be near a local optimum of the relaxed objective (eq. (2). since we have stopped making progress towards the relaxed objective for the current value of a. However, this might be close local optimum of the actual objective function eq. ① By increasing a at this stage, we make the relaxed objective closer approximation to the real objective; we continue optimization until we are close to local optimum of the new relaxed objective, and then repeat. We find that this annealing approach worked well in practice. Figure T shows comparison of temperature annealing to optimization with fixed sigmoid temperature parameters. can be seen that the annealing approach improves over every fixed setting of the parameter.
Threshold Query Answering with RAP++
We described the tools for optimizing the relaxed objective in Eq. 2 In this section, we introduce our private synthetic data generation algorithm RAP++ for mixed-type data (Alg. D. RAP++ accepts as input mixed-type data and supports releasing answers to both mixed marginal and class conditional threshold queries. Our approach for synthetic data generation differs from prior work in that previous mechanisms MSM19 MMSM22 GAH+ VTB 20 ABK 22 only operate on discrete data for answering categorical marginal queries. For mixed-typp type data, could simply discretize the data and rum one of the previously known mechanisms, however, we will show that directly optimizing over threshold based queries has advantage in terms of accuracy and scalability.
Given an input dataset E x and collection statistical queries Q, RAP++ operates over sequence of T rounds to produce synthetic dataset that approximates D on the queries Q. First,

---

RAP initializes a relaxed synthetic dataset D2 E An. of size â. uniformly at random from the data domain of the original dataset. On each round t 1...., T, the algorithm then calls the RN mechanism to select K queries (denoted by Q+) on which the current synthetic data Dr is a poor approximation, and uses the Gaussian mechanism to privately estimate the selected queries. Using these new queries and noisy estimates, the algorithm calls algorithm | synthetic dataset D++1, such that D is consistent with D on the current set of queries Qz. The process continues until the number of iterations reach T.
to solve
2 and find the next
The way algorithm RAP is described in algorithm 2 is specific to the setting of answering threshold- based queries, since it uses temperature annealing step which applies only to queries which use sigmoid threshold functions like mixed marginals (definition B or linear threshold queries (definition 4 We can also use the algorithm to handle non-threshold based queries such categorical marginals but in this case our algorithm reduces to the RAP algorithm due to [ABK We can also the algorithm using multiple query classes, using threshold annealing for those query classes on which it applies.
Differential Privacy The algorithm's 's privacy analysis follows from composition of a sequence of RN and Gaussian mechanisms, which is similar to other approaches that select queries adap- tively [HRUTT GRUI2 HLMI2 ABK privacy guarantee.
VTB 20 LVW21. The following theorem states the
Theorem (Privacy analysis RAP++). For any dataset D, any query class Q, any set of parameters K, T, á, 01, and any privacy parameters 5 > 0, Algorithm 2 satisfies (c, 6) -ddfffeerettial privacy.
Proof of theorem
I follows the composition property of p-zCDP. We defer the proof to the appendix.
The accuracy of our method (algorithm 2 for answering a collection of statistical queries depends mainly on the success of our optimization oracle (algorithm D Since the oracle algorithm is a heuristic, we cannot provide a formal accuracy guarantee. However, the paper provides empirical evidence of the oracle's 's performance.
Accuracy
We remark that the work of AAB 211 provided accuracy guarantees for RAP under the assumption that their oracle solves the optimization step perfectly. Our method, which is instantiation of RAP with new query classes, inherits RAP accuracy guarantees (again, under the assumption that the optimization problem ( can be solved).
5 Experiments
The experiments are performed over a collection of mixed-type real-world public datasets. The quality of generated synthetic datasets is evaluated in terms of the error set of mixed-marginn queries as well as on their usefulness for training linear models using logistic regression. We compare our method RAP++ against existing well-known algorithms for synthetic data generation, including PGM [MMM19. DP-MERF [НРР2]) CTGAN [FDK22), RAP [ABK+21], We use the adaptive version of PGM, which is called MWEM+PGM in the original paper. We compare our algorithm RAP++ with all other algorithms at various privacy levels quantified by e. with ó always set to be 1/n² for all algorithms.
Datasets. We use a suite of new datasets derived from US Census, which are introduced in [HMS21]
These datasets include five pre-defined prediction tasks, predicting labels related to income, em- ployment, health, transportation, and housing. Each task defines feature columns (categorical and numerical) and target columns, where feature columns are used to train a model predict the target column. Each task consists of subset of columns from the American Community Survey (ACS) corpus and the target column for prediction. We use the five largest states (California, New York, Texas, Florida, and Pennsylvania) which together with the five tasks constitute 25 datasets. We used the folktables package IDMSST extract features and tasks In the appendix, we include table that summarizes the number of categorical and numerical features for each ACS task and the number of rows in each of the 25 datasets.
'The Folktables package comes with MIT license, and terms of service of the ACS data can be found here: http://wwww.oonggggaaaaddeeeeebs serveeee..
7

---

We are interested in datasets that can be used for multiple classification tasks simultaneossl.. To this end, we create multitask datasets by combining all five prediction tasks. The result is five multitask datasets corresponding to five states, where each multitask dataset has five target columns for prediction. The learning problem given multitask dataset per state consists of learning five different models, one to predict each of the target columns from the feature columns. Each multitask dataset has 25 categorical features, 9 numerical features, and five target binary labels.
5.1 Statistical Queries
Here, we describe three different classes of statistical queries that were used either for synthesizing datasets for evaluation. First, introduce some notations. Given input a dataset with columns [d]. let C, R. L be a column partition of [d]. where C, R, and L denote the categorical features, numerical features, and target columns for ML tasks, respectively.
Class Conditional Categorical Marginals (CM). This class of queries involve marginals defined over two categorical feature columns and one target column, making it a subset of 3-way categorical marginal queries. Using notation from definition 2 this query class is defined as Qeat {(s.y (C x C x L) y Xs). This query class is constructed to preserve the relationship between feature columns and target columns with the goal of generating synthetic data useful for training ML models. Since the possible set of queries for this class is finite we enumerate over all possible combinations of 3-way marginals in our experiments.
Class Conditional Mixed-Marginale (MM). Similar to the class conditional categorical marginals, we create 3-way marginal queries involving two feature columns and one target column. For this query class, however, we use only numerical columns for the features as opposed to CMs. Since the possible set of marginals involving numerical features is infinite, we use 200, 000 random 3-way mixed marginal queries in our experiments.
Class Conditional Linear Thresholds (LT). Next we deseribe the construction of the class condi- We generate a set Qun of m = 200, 000 random
tional linear threshold queries using definition g queries, which is populated as follows:
1. Generate random vector Ô E R4RR,, where the value of each coordinate i E R is sampled as
0. ~ (0, 1). Then set 0 = 0/vd.
2. Sample a threshold value r from the standard normal distribution, i.e., ~~ (0,,
Sample a label E L and a target value for the label y E X,
4. Add the query Rt.0. to the set Qtin-
In the experiments that follow, RAP++ is trained both with the CM queries and the class conditional linear threshold queries. PGM and RAP are trained with the CM queries over their discretized domain (i.e. bin the numerical features so that they become categorical, then run the algorithms to preserve CM queries). We use MM queries mainly for evaluation (see fig.
Experimental Setup. For both RAP and PGM discretized all numerical features using an equal-sized binning, and compare the performance for numbers of bins in (10, 20, 30, 50, 100). For the results, we choose 30 bins for discretization, it performs well overall across different tasks and privacy levels. In the appendix we show more results for different choices of bin size. The other relevant parameter for both PGM and RAP is the number of epochs of adaptivity, which is fixed to be d - 1, where d is the number of columns in the data.
Next we describe the relevant parameters used to train RAP++... Since RAP++ optimizes over two query classes (CM and LT), the first parameter TcM corresponds to the number of adaptive epochs for selecting CM queries. The other parameter TLT corresponds to the number of adaptive epochs for selecting LT queries. To be consistent with PGM and RAP we always choose TcM = dicı 1, where dic is the number of categorical columns in the data. Finally, K is the number of queries selected per epoch as described in algorithm 2
We fix the parameters of RAP++ to be Tir 50 and K = 10 since it works well across all settings our experiments. Figure shows the effect of different hyperparameter choices for both RAP++ and PGM It can be seen that RAP++ achieves better accuracy in less runtime than PGM Furthermore, RAP+ not very sensitive to varying TET, whereas PGM performance is very sensitive to the bin-size. For implementation details, see the appendix.
8

---

Queries
Task Income
Tesk
NM
0.010
0.015
0.00
0,005
001
epallon
epsilon
apsilon
Figure 2: Summary of average error for Mixed Marginals (MM) three tasks and aggregated over five ACS states. Each column represents different task. We only compare against the most competitive approach PGM See appendix for other approaches and CM queries. RAP++ consistently achieves lower error, especially at small values.
5.2 Main Results
Mixed-Marginals Evaluation. We begin by comparing RAP++ against PGM on how well the generated synthetic data approximates set of random MM queries 25 single-task ACS datasets (see appendix). We use PGM as our primary baseline because it was the most performant of the various approaches
tried DD-MERR- CTGAN and RAP), Here tasks only for MM queries in fig. and the remaining tasks, and CM query results are shown in the appendix. Note that these experiments, the difference between RAP and RAP++ in how it treats numeric valued features and threshold -bseed queries. In particular, for CM queries, RAP and RAP++ are essentially the same, so it does not make sense to compare RAP and RAP++ in this setting.
show results on three
The figure shows average errors across all states for each task with respect to c. For each task/state/epsilon setting, compute the average error over the set of queries (either CM MM queries). Then we take another average over states for each task/epsilon. On average, RAP++ performed slightly better answering CM queries, and significantly improved the average error on MM queries across all tasks. Note that none of the approaches used MM queries in training, hence the results indicate better generalization capability of RAP++.
ML Evaluation. We also evaluate the quality of syn- thetic data for training lin- ear logistic regression mod- els. For each dataset, we 80 percent of the rows as a training dataset and the remainder test dataset. Only the training dataset is used generate synthetic datasets subject to differen- tial privacy. We then train logistic regression model on the synthetic data and evalu- ate it on the test data. Since labels are not balanced in individual tasks, model per- formance is measured us- ing Fl score which is har- monic mean of precision and recall. Also there isn't clear definition of the positive class in each task, report the macro Fl score, which the arithmetic mean Fl scores per class. As a "gold-standard" baseline, we also train model on the original training set directly (i.e. without any differential privacy protections).
0.15 Texk Incone
0.5
042
1.2 Tax wiromm
1.0 Taak andfaymnnt
2-000 caveaay
0.5
040
004
Figure 3: Fl score vs. Runtime Comparing RAP++ (blue) and PGM (orange) for different hyperparameter choices over three ACS single-task datasets and
{0.15, 1}. PGM parameter bin-size is varied by selecting from {10, 20, 50, 1003. RAP++ parameter for the number of epochs for linear thresholds (TLT) is varied by selecting from {10, 30, 50, 70}.
The ML evaluation contains both single-task and multitask experiments. Since single-task datasets only define one column as the target label for prediction, we train one logistic regression for each single-task dataset. Figure. 4 summarizes our results on single-task datasets and Fig. 5 shows results on multitask ones. On single-task, RAP++ clearly outperforms every other benchmark in terms of FI score across tasks and privacy levels. Due to the space limit, we only show results for three tasks and single state, while the remaining set of experiments can be found in the appendix.

---

For multitask experiments, we observe that our algorithm most significantly outperforms PGM in terms of Fl score on the income task, where numerical features are more important. On the coverage tasks R A wins when e is small. And finally, PGM does slightly better on the employment task where numerical columns provide no information. To understand when numerical features are important, we conducted simple experiment where we trained logistic regression model on all features (including numerical) and compared against a model trained only on categorical features. We show that numerical features are important for the income task and less important for other tasks. See appendix for details on this. Our experiments confirm that RAP++ produces synthetic data which can train more accurate linear models when the numerical features are important for the prediction task.
State NY| Task- income
State NY Task moloyment
State NY Task coverage
(mocno)
0.07
625
25
07
0.5
032
0,07
025
epallon
Figure 4: ACS Single-task ML: Comparison of synthetic data generation approaches by the Fl score
achieved on linear models trained on synthetic data and Fl score achieved by training on original dataset(blac) dotted line). Results averaged across three single-task datasets (ACS-NY state) for different privacy levels. See Appendix for other states.
RAP
Stato
Income
State
Taik- enooomment
State NY coverage
1.0
F3
0.6
0.04
0.07
0.
0.00
0.07
0.00
0.77
02
5.000
acslon
Spcion
epston
Figure 5: ACS Multitask ML: Comparison of synthetic data generation approaches using multitask
datasets by the Fl scores achieved on linear models trained on synthetic data and Fl score achieved by training on original dataset(black dotted line). See Appendix for other states.
6 Limitations and Conclusions
We propose an algorithm for producing differentially private synthetic data that improves on prior work in its ability to handle numeric valued columns, handling them natively rather than binning them. We show that this leads to substantial runtime and accuracy improvements on datasets for which the numerical columns are numerous and relevant. For machine learning tasks on categorical data or for data for which the numerical features are not informative, prior methods like PGM can still sometimes produce more accurate synthetic data, although we still generally outperform in terms of runtime. Producing synthetic data useful for downstream learning beyond linear classification largely remains open: In our experiments, more complicated models trained on the synthetic data generally resulted in performance that was comparable or slightly worse than the performance of linear models trained on the synthetic data, even when the more complex models outperformed linear models the original data. Note that it is not so much that the non-linear methods perform poorly in an absolute sense, but they fail to realize the performance gains beyond that achievable by linear models when applied to the private synthetic data. Producing high quality synthetic data that can enable downstream machine learning that obtains higher accuracy than linear models a very interesting question.
10

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We currently focus on providing
private synthetic data for downstream ML tasks with linear models.
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any assets either in the supplemental material URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
The ACS dataset was released by the US Census Bureau publicly, and we follow the terms of service of the ACS data in our use. The terms of service can be found here:
(e)
Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
According to the Terms of Service https://www.censuus httss//wwww.nssu...////d/d/dddd/ wwtps///ww///eedee/////////eee/e
of-service. htmll of the ACS data, "The Census Bureau has created these data to exclude information that would directly identify respondents and characteristics that may lead the identification of respondents." and ... users will not use these data, alone or in combination with any other Census or non-Census data, to identify any individual person, household, business or other entity; not link or combine these data with information in any other Census or non con-Census dataset in manner that identifies an individual person, household, business or other entity; not publish information from these data files, particularly in combination with any other Census or non-Census data, in manner that identifies any individual person, household, business or other entity; and not use the identity of any person or establishment discovered inadvertently. ... We follow the Terms Service in our use of the ACS data.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
11

---

References
[ABK*21] Sergül Aydöre, William Brown, Michael Kearns, Krishnaram Kenthapadi, Luca Melis, Aaron Roth, and Ankit A. Siva. Differentially private query release through adaptive projection. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th Interna- tional Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 457 PMLR, 2021.
[ALMM19] Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private pac learning implies finite littlestone dimension. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 852 860, 2019.
[BFH 18] James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman- Milne, and Qiao Zhang. JAX: composable transformations of Python+NumPy pro- grams, 2018.
[BJWW 19] Brett K Beaulicu-Jones, Zhiwei Steven Wu, Chris Williams, Ran Lee, Sanjeev P Bhavnani, James Brian Byrd, and Casey Greene. Privacy-preserving generative deep neural networks support clinical data sharing. Circulation: Cardiovascular Quality and Outcomes, 12(7):e005122, 2019.
[BLR08] Avrim Blum, Katrina Ligett, and Aaron Roth. A learning theory approach to non- interactive database privacy. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 609-618, 618, 2008.
[BNVV15] Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil Vadhan. Differentially private release and learning of threshold functions. In 2015 IEEE 56th Annual Symposium Foundations of Computer Science, pages 634-649. IEEE, 2015.
[BS16a] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, pages 635-658. Springer, 2016.
[BS16b] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, pages 635-658. Springer, 2016.
[DHMS21] Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair machine learning. Advances in Neural Information Processing Systems, 34, 2021.
[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006.
[DNR + 09] Cynthia Dwork, Moni Naor, Omer Reingold, Guy N Rothblum, and Salil Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In Proceedings of the forty-first annual ACM symposium Theory of computing, pages 381-390, 2009.
[DR19] David Durfee and Ryan M Rogers. Practical differentially private top-k selection with soy--hat-you-get composition. Advances in Neural Information Processing Systems, 32, 2019.
[FDK22] Mei Ling Fang, Devendra Singh Dhami, and Kristian Kersting, Dp-ctgan: Differen- tially private medical data generation using etgans. Artificial Intelligence Medicine (AIME), 2022.
[GAH+ 14] Marco Gaboardi, Emilio Jesús Gallego Arias, Justin Hsu, Aaron Roth, and Zhi- wei Steven Wu. Dual query: Practical private query release for high dimensional data. In International Conference Machine Learning, pages 1170-1178. PMLR, 2014.
12

---

[GHRUTI] Anupam Gupta, Moritz Hardt, Aaron Roth, and Jonathan Ullman. Privately releasing conjunctions and the statistical query barrier. pages 803-812, 2011.
[GHV20] Marco Gaboardi, Michael Hay, and Salil P. Vadhan. A programming framework for opendp. 2020.
[GRU12] Anupam Gupta, Aaron Roth, and Jonathan Ullman. Iterative constructions and private data release. In Theory of cryptography conference, pages 339-356. Springer, 2012.
[HAP21] Frederik Harder, Kamil Adamczewski, and Mijung Park. Dp-merf: Differentially private mean embeddings with randomfeatures for practical privacy-preservnng data generation. In International Conference on Artificial Intelligence and Statistics, pages 1819-1827. PMLR, 2021.
[HLM12] Moritz Hardt, Katrina Ligett, and Frank McSherry. A simple and practical algorithm for differentially private data release. In Advances in Neural Information Processing Systems, pages
2012.
[HR10] Moritz Hardt and Guy Rothblum. multiplicaaiie weights mechanism for privacy- preserving data analysis. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 61-70. IEEE, 2010.
[HRS20] Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis of online and differentially private learning. Advances in Neural Information Processing Systems, 33:9203-922 9215, 2020.
[HT10] Moritz Hardt and Kunal Talwar. On the geometry of differential privacy, In Proceedings of the sorty-second ACM symposium on Theory of computing, pages 705-714, 2010.
[JYdd118] James Jordon, Jinsung Yoon, and Mihaela van der Schaar. Pate-gan: Generating synthetic data with differential privacy guarantees. In International Conference on Learning Representations, ICLR '18 2018.
[Kea98] Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 45(6):983-1006, 1998.
[LVW21] Terrance Liu, Giuseppe Vietri, and Zhiwei Steven Wu. Iterative methods for private syn- thetic data: Unifying framework and new methods. arXiv preprint arXiv:2106.07153, 2021.
[MMSM22] Ryan McKenna, Brett Mullins, Daniel Sheldon, and Gerome Miklau, Aim: An adaptive and iterative mechanism for differentially private synthetic data. arXiv preprint arXiv:2201. /2677, 2022.
[MPSM21] Ryan McKenna, Siddhant Pradhan, Daniel R Sheldon, and Gerome Miklau. Relaxed marginal consistency for differentially private query answering. Advances in Neural Information Processing Systems, 34, 2021.
[MSM19] Ryan McKenna, Daniel Sheldon, and Gerome Miklau. Graphical-model based estima- tion and inference for differential privacy. In International Conference on Machine Learning, pages 4435-4444. PMLR, 2019.
[NTZ13] Aleksandar Nikolov, Kunal Talwar, and Li Zhang. The geometry of differential privacy: the sparse and approximate cases. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 351-360, 2013.
[NWD20] Marcel Neunhoeffer, Zhiwei Steven Wu, and Cynthia Dwork. Private post-gan boosting. arXiv preprint arXiv:2007. /934, 2020.
|PGM + 19] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmai- son, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjic Bai, and Soumith Chintala.
13

---

Pytorch: An imperative style, high-performance deep learning library. In H. Wal- lach, Larochelle, A. Beygelzimer, d'Alché-Buu Buc, E. Fox, and Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024-8035. Curran Associates, Inc., 2019.
[RRIO] Aaron Roth and Tim Roughgarden. Interactive privacy via the median mechanism. In Proceedings of the forty-scennn ACM symposium Theory of computing, pages 765-774, 2010.
[TMH* Yuchao Tao, Ryan McKenna, Michael Hay, Ashwin Machanavajjhala, and Gerome Miklau. Benchmarking differentially private synthetic data generation algorithms. arXiv preprint arXiv:2/ 12. 12.0238, 2021.
[VTB+20] 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.
XXL 18] Liyang Xie, Kaixiang Lin, Shu Wang, Fei Wang, and Jiayu Zhou. Differentially private generative adversarial network. arXiv preprint arXiv:1802.067555 2018.
14


Reviews:
[{"review_id": "uc7_CAFay4W", "reviewer": "Reviewer_DNy5", "summary": "The paper iterates upon the \"Relaxed Adaptive Projection (RAP)\" framework from [ABK+21], a \"moment matching approach\" for generating private synthetic data. The primary improvement wrt to the prior work is the ability of handling a mixture of both categorical and numerical features --- where RAP requires a discretization of the numeric domain via binning. This is achieved in two steps: (1) numeric based queries are introduced (which are different types of threshold queries); and (2) a differentiable approximation to these numeric queries are introduced with via a tempered sigmoid annealing query. The later is key in the optimization of the private synthetic data. With these tools to handle numerical based queries, differential privacy mechanisms are used to ensure that the synthetic data is private.\n\nIn summary, the approach can be broken down as follows:\n1. The K worst query functions are selected wrt error and using \"Report Noisy Top-K\", a DP mechanism;\n2. The values of these queries are calculated with the Gaussian DP mechanism;\n3. The query functions in (1) are converted to their differentiable approximations;\n4. A projection step occurs using results of (2) and (3) to find the best data wrt error.\n\nThese steps done in the paper's Algorithm 2. The proof of $ (\\epsilon, \\delta) $-DP follows from standard composition and post-processing properties of zero concentration DP.\n\nExperimentally, the paper uses their approach to generate synthetic data for multitask learning (multiple columns of labels to target in classification). With this in mind, the paper evaluates their approach over many variants of the ACS dataset. The results present appear promising for both mixed-marginal query evaluation and (linear) classification.\n", "questions": "Comments / Suggestions / Questions\n1. Comparison of Fig 2 & 5 for all approaches is not present in Appendix. This seems to be key in evaluating RAP++, especially examining the difference between RAP and RAP++ for CM to see if RAP++ is strictly better.\n2. Fig 1. seems a bit odd without it specifying the experiment it comes from.\n3. What if any of the bound on query error for RAP [ABK+21] can be \"inherited\" for RAP++? In particular for the numerical queries.\n4. The initialization of synthetic dataset doesn't seem to be discussed anywhere, Algorithm 2, Line 3.\n5. Algorithm 1/2 is slightly confusing as it appears to suggest that temperature scaling is utilized even for CM queries (which from digging into the code is not the case). Clarification on the specifics of the loss functions for different queries would be helpful. Furthermore, stating the case in which RAP++ reduces to RAP explicitly would be helpful for the reader (which I believe occurs when all queries are CM type).\n6. The limitation section states that \"Producing synthetic data useful for downstream learning beyond linear classification largely remains open\". Do non-linear classifiers perform poorly on RAP++? Plots of failure cases would be interesting to see for this case.\n\nMinor typos\n  - Algorithm 1. Line 5: \"Stating\" -> \"Starting\"\n  - Algorithm 1. Line 5: Should \"$D_{k}$\" be \"$D_{j}$\"?\n  - Algorithm 1. Line 5: Should \"[...] descent on $\\hat{D}$\" be \"[...] descent on $L_{j}(\\hat{D})$\"?\n  - Line 227: \"Eq. 2\" is inconsistent with equation citation in previous parts of the paper.", "limitations": "The author states the limitation for ML downstream tasks to that of only linear classification. It would be useful to see explicit experiments on non-linear classifiers trained on RAP++ synthetic datasets.\n\n---\n\nEdit: Addressed in the reviewer discussion. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n  - The paper presents an iterative improvement over RAP. This is particularly shown in the experimental section, where RAP++ is competitive or superior to other prior work.\n  -  The explanation and motivation for the tempered sigmoid, the subsequent queries, and annealing approach was good.\n\nWeaknesses\n  - Although there is a privacy guarantee and promising experimental results, there is not an theoretical error analysis. From briefly looking at [ABK+21], RAP has a bound on query error.\n  - There are a few unclear aspects of the paper.\n  - Fig 2 & 5 cites the Appendix for comparison against other approaches, but this does not appear in the Appendix.\n\nPoints which could be rephrased as questions / comments are reiterated below.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "rAbqvCtEvCX", "reviewer": "Reviewer_vqTp", "summary": "This paper provides a method for generating synthetic differentially-private datasets for use in answering statistical queries without the need for binning.  Specific query types that were analyzed include Mixed Marginal Queries, Class Conditional Linear Threshold Queries, and \"Querying the Error.\"  The is an improvement over previous work for certain classes of statistical queries.", "questions": "Can you address what bounds are given for this algorithm, eg on added error?\nWhere do the main technical innovations of this paper lie?", "limitations": "Yes, the limitations have been addressed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main improvement in this paper is for the case of mixed-type queries queries, which contain a mixture of categorical and numerical features. The technique in the paper is an extension of the \"relaxed projection mechanism\" by considering the k hardest queries and also adding a simulated annealing step.  The experimental results are also impressive.  Overall, this would be a worthwhile contribution.\n\nHowever, I do have some concerns: One question I had is about the lack of theorems in the paper.  Epsilon-delta privacy follows straightforwardly from the addition of the noise, how about other components, eg added error?  Another thing that would help if the authors explained the where the main difficulty of applying these known techniques lies.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "X_kAfS-x3wY", "reviewer": "Reviewer_cmFo", "summary": "The paper considers the problem of privately generating synthetic datasets based on a private dataset for which each data point is a mix of numerical and categorical variables. The best-performing past approach in this area is an approach called moment-matching, which tries to generate a synthetic dataset that minimizes the error of marginal queries (i.e., queries that take 0-1 variables x_i, and ask for the expectation of $\\prod_{i \\in S} x_i$) made on the synthetic database. They build off an algorithm called RAP, which repeatedly (privately) chooses new marginal queries for which the current synthetic database has high error, and then tries to minimize the error on all queries chosen so far. Past approaches made numerical variables suitable for marginal queries by placing them into bins (thus making them categorical); the authors argue the binning heuristic is impractical. They instead propose two new classes of queries. The first applies a threshold to the numerical variables to turn them into 0-1 variables. The second applies a linear classifier to a subset of the numerical variables to generate a 0-1 variable. \n\nThe most challenging step in the RAP algorithm is to, after choosing a set of queries, find a synthetic dataset that minimizes the error on these queries. RAP does this by defining a fractional relaxation of synthetic datasets and an error function over fractional datasets, which allows one to use continuous optimization techniques. The authors propose RAP++, which is RAP, but also with the option to choose queries from their two proposed classes. To make the error function differentiable, the authors approximate the threshold/linear classifier in the queries with a sigmoid function. However, a sigmoid function has to either be highly non-smooth (which makes it hard to optimize over) or poorly approximate threshold functions. The authors propose that rather than doing a one-shot optimization over the error function defined using sigmoids, instead using an annealing-style algorithm that repeatedly solves the optimization problem, but each time decreases the temperature of the sigmoids. \n\nIn experiments, the authors compare RAP++ to several other synthetic data generation methods in the literature. The authors show that RAP++ produces synthetic datasets with better accuracy/error than the other methods in most settings. However, since RAP++ places less emphasis on marginal queries just on categorical data in its training process, in tasks where numerical data is not useful it is outperformed by some other methods. The authors also show the runtime of RAP++ is much less than the runtime of the next-best method in their experiments.", "questions": "My two main questions/concerns are regarding the experiments:\n\n-How were the algorithms the authors compared against chosen? In particular, it seems like in [TMH+21] https://arxiv.org/pdf/2112.09238.pdf (which the authors cite), they state that an algorithm called MST frequently performs well in a series of benchmarks; in particular, it seems to outperform 3 of the 4 benchmark algorithms tried in this paper. However, the authors did not compare to MST. Was there a reason MST wasn't chosen?\n\n-As far as I can tell, even after looking in the appendix, the only benchmark to which the authors made a runtime comparison is PGN. This seems to be motivated by the fact that PGN is the best performing of the benchmarks. However, the results presented in the paper don't seem to preclude the possibility of another algorithm having better runtime/scalability than RAP++ at the cost of having a higher error as well.\n\nEDIT: After reading the authors' rebuttal, I feel both questions have been addressed and are not of concern.", "limitations": "Aside from the concerns in \"questions\", I don't believe there are any major limitations or negative social impacts not addressed by the authors.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: To the best of my knowledge, while the algorithm in this paper builds upon a pre-existing algorithm (RAP), the two improvements made to that algorithm (new types of queries, and an annealing method for optimization) are both fairly original. Furthermore, the problem is fairly well-studied, so a new approach for the problem is more novel than perhaps, say, a new approach appearing in the second or third paper on a problem.\n\nQuality: The methods the author propose appear to be very natural despite their originality/novelty. The privacy guarantees of the algorithm are sound and easy to see. The experiments appear to be fairly extensive and support the authors' claims. I do have some questions/concerns about the experiments, however, which I have placed in the questions section of the review.\n\nClarity: I thought that the paper was very clean from an exposition standpoint. The introduction does a good job explaining the issue with past approaches, and when explaining the algorithm I felt the design decisions the authors made were well-motivated by their explanation of the problems those decisions addressed. There are some clarity issues with the experimental design/results related to my questions/concerns from the previous bullet.\n\nSignificance: I think the paper is fairly impactful; synthetic data generation is a well-studied problem that many practitioners are trying to solve in production. In turn, algorithms like the RAP++ algorithm proposed in this paper have a reasonable chance to be deployed in practice on wide scales.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept