An Uncertainty Principle is a Price of Privacy-Preserving Microdata
Authors: John M. Abowd
Robert Ashmead
Ryan Cumings-Menon
Simson L. Garfinkel
Daniel Kifer
Philip Leclerc
William Sexton
Ashley E Simpson
Christine Task
Pavel Zhuravlev
Venue: NeurIPS 2021 Poster (2021)
Keywords: differential privacy
synthetic data

Abstract: Privacy-protected microdata are often the desired output of a differentially private algorithm since  microdata is familiar and convenient for downstream users. However, there is a statistical price for this kind of convenience. We show that an uncertainty principle governs the trade-off between accuracy for a population of interest (``sum query'') vs. accuracy for its component sub-populations (``point queries''). Compared to differentially private query answering systems that are not required to produce microdata, accuracy can degrade by a logarithmic factor. For example, in the case of pure differential privacy, without the microdata requirement, one can provide noisy answers to the sum query and all point queries while guaranteeing that each answer has squared error $O(1/\epsilon^2)$. With the microdata requirement, one must choose between allowing an additional $\log^2(d)$ factor ($d$ is the number of point queries) for some point queries or allowing an extra $O(d^2)$ factor for the sum query. We present lower bounds for pure, approximate, and concentrated differential privacy. We propose mitigation strategies and create a collection of benchmark datasets that can be used for public study of this problem.


An Uncertainty Principle is a Price of Privacy-Preserving Microdata
John Abowd U.S. Census Bureau and Cornell University
Robert Ashmead U.S. Census Bureau
Ryan Cumings-Menon U.S. Census Bureau
Simson Garfinkel
Daniel Kifer U.S. Census Bureau and Penn State University
Philip Leclere
(formerly) U.S. Census Bureau U.S. Department of Homeland Security and George Washington University
U.S. Census Bureau
William Sexton
Ashley Simpson
Christine Task Knexus
Pavel Zhuravlev
(formerly) U.S. Census Bureau and Tumult Labs
Knexus
U.S. Census Bureau
Abstract
Privacy-protectee microdata are often the desired output of a differentially pri- vate algorithm since microdata is familiar and convenient for downstream users. However, there is a statistical price this kind of convenience. We show that uncertainty principle governs the trade-off between accuracy for population interest ("sum query") vs. accuracy for its component uub-populations ("point queries"). Compared to differentially private query answering systems that are not required to produce microdata, accuracy can degrade by a logarithmic factor. For example, in the case of pure differential privacy, without the microdata require- ment, one can provide noisy answers to the sum query and all point queries while guaranteeing that each answer has squared error O(1/c².. With the microdata requirement, one must choose between allowing additional log log2(d) is the number of point queries) for some point queries or allowing an extra (d
(d) factor (d
factor for the sum query. We present lower bounds for pure, approximate, and concentrated differential privacy. We propose mitigation strategies and create a collection benchmark datasets that can be used for public study of this problem.
Introduction
Differential Privacy [16] is a mathematical theory of information leakage that allows organizations to publish noisy statistics about their datasets while protecting the confidentiality of user information. Its state-of the-art guarantees have resulted in adoption by data collectors such as the U.S. Census
Bureau 31 10
D. Google 19 6),
Apple [37]. Microsoft
[13] Uber (26), and Facebook [33].
In many cases, downstream users want the output of disclosure avoidance systems in the form of microdata (a set of records about individuals). For example, this has historically been the case for tabulations of Census Bureau data, and is currently a requirement for most 2020 Census of Population and Housing tabulations(20) However, end-user study of demonstration data products released by an early prototype of the Census Bureau's 's disclosure avoidance system showed significant
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

anomalies in the privacy- protected microdata [3 They noted the following: the system first produced differentially private noisy query answers, called measurements, and then synthesized privacy-protected microdata so that query answers computed from the privacy-protected microdata matched the noisy measurements as closely as possible (based on some objective function). However, after the iriaacyprotecctd microdata were created, they compared (1) the original measurement query noisy answers and (2) the values of the same queries computed from the privacy-protected microdata. They noted that in some cases, the query error from the privacy-protectee microdata was "much larger" than the measurement query error
In this paper, we show that such anomalies are an inherent and unavoidable consequence of privacy- protected microdata (they affect all differentially private algorithms that must output microdata). We further show that the additional errors caused by new uncertainty principle that trades off error between accuracy on populations and accuracy on sub-populations. We next explain this principle.
microdata also satisfy
First, our criterion is per-query expected squared error. That is, if Q a collection of queries, D is the true data, and is the privacy-protected microdata, we are interested the left side of Equation (below), where the expectation is taken over the randomness of the algorithm that ingests D and outputs privacy protected D.
max (5((((D) (D)) QEQ
<
E (max((()))9(0) qEQ
Our focus: per-query ervor
Most other papers: simeltanccos//uttier error.
This metric measures whether there exist "bad" queries that have systematically large errors on average. It is not to be confused with simultancous/outtirr noise error (right side of Equation I that is the focus of most theoretical papers on differential privacy, such as 7 The reason is that simultaneous error cannot distinguish between systematic error in specific queries vs. outliers that result by chance when dealing with many random variables. On the other hand per query- can make this distinction because it considers the average behavior of each query separately.
Next, consider a collection of d disjoin counting queries .I...., Qd and a special query q. that is equal to their sum (g. (2) = Σ, (2)). We call . Qd the point queries and q. the sum query. Examples include (1) q. 2 ) = "# of Black or African Americans in the data living in California" and (D) "# of Black or African Americans in the data living in county in California" and (2) q. (I) "population of a given county" (which can be used in federal and state-level funding allocations) and (2) = "population in census block in that county" (useful for redistricting). Thus, for different use-cases, accuracies at these local and aggregate scales important.
is well-known that queries .I,..., Id: 2. can be answered using -differrnntill privacy by adding Laplace(2/c) noise to each query [18), thus guaranteeing that each query answer has expected squared error 8/e². However, in this paper, we show that it is not possible to guarantee this kind of error if one is required to produce differentially private microdata D and answer queries using it (i.c., computing (()))......())))) q- (D)). Specifically, suppose an e-differentially private microdata- producing algorithm can guarantee that, for all datasets D, E (gg (2) (i)))) D and max, E (2) -q, ( < C2 for some constants C' and D. Then one has to choose:
If D2 E ((1/22) then C2 E 2 (d)). That is, making the sum query accurate may force us to take lod penalty in the expected squared error some of the point queries, or
If C2 E O(1/e²) then D2 ( That is, a low per-query error guarantee for point queries may increase expected squared error of the sum query by a factor of d?.
We present such lower bound results for pure differential privacy [66, approximate differential privacy 15), and concentrated differential privacy [8) with nearly matching upper bounds.
'Throughout this paper we use privacc-prrtected and privacy-preserving synonymously. The Census Bureau prefers univacy-protectern whereas the scientific literature has often used "privacy- "ereaccppeeeerving"" " Both terms mean that the confidentiality of individual responses has been protected using differentially private algorithms.
That is, adding/removing record into the data can only affect the answer to one of the queries.

---

We note that this uncertainty principle affects some, but not all, possible datasets. That is, there are datasets for which the error penalties do not exist. Thus. the goal practical microdata generation should be to minimize the occurrence of this uncertainty principle (since eliminating entirely impossible). To this end, we propose benchmark suite of real and synthetic datasets that can be used by the wider community for further study of this problem. We also propose some algorithms, inspired by our lower and upper bound proofs, for mitigating the effects this uncertainty principle. Limitations: empirically, these algorithms perform well on the benchmarks but we not have theoretical proofs performance.
Preliminaries
Let D denote dataset, M differentially private algorithm, and let 2 be (e.g., (2) D). A counting query q is associated with a predicate 1., and the query answer ((D) is the number of records in D that satisfy v. We let q1,..., qa represent a set of d counting queries whose corresponding predicates .i...., Da are disjoint (no record can satisfy more than one of the predicates). We also let y. denote their sum: q. (2) = > (D).
dataset
2.1 Differential Privacy
Differential privacy is currently considered the gold standard in privacy protections. It relies on the concept of neighboring datasets, defined follows.
Definition (Neighbors). Two datasets D and D2 are neighbors. denoted by D1 D2. D can be obtained from D2 by adding or removing one record.
Using this concept of neighbors, differential privacy ensures that adding removing record from a dataset has little effect on the probabilistic outcomes an algorithm:
Definition (Differential Privacy (16)). Given privacy parameters
and 2 randomized algorithm M satisfies (c, 8)-DP if for all pairs of datasets D1, D2 that are neighhors of each other, and for all S C rrane(M) (M), the following equation holds:
P(M(2)) E S) S P(M(()) E S) +
where the probability is only over the randomness in M (not the randomness the data). When 5 = O, we say that M satisfies pure differential privacy (also known as e-differential privacy or e-DP) and when we say that M satisfies approximate differential privacy.
Another important version of differential privacy, is p-7CDP (concentrated differential privacy):
Definition (ZCDP R) Given a privacy parameter P. randomized algorithm M satisfies p-zCDP for all pairs of datasets D1, D2 that neighbors of each other and all numbers 1,
D. D.(M(D))IIM S pc
where Da(PIIQ)= = a log E ((a)==-)) [
is the Renyi divergence of order between proba-
bility distributions P and Q.
Although zCDP is difficult to interpret, there are useful results that help provide intuition. First, any M that satisfies e-differential privacy also satisfies p-zCDP with p 2 g In general a p-zCDP algorithm does not satisfy pure differential privacy but does satisfy (c, 6) for infinitely many pairs of and ó that lie along a curve (see and [2 for conversions between p-zCDP and (e, (DP)).
2.2 Algorithm Design with Differential Privacy
few basic principles underlie the construction of many algorithms for differential privacy. The first is sensitivity, which measures the maximum impact that one record can have set of queries (regardless of input data):
Definition (Sensitivity [6]). The Lp global sensitivity of set Q queries, denoted by Ay( 1/2
defined as sup DIND2
(Ege (g(D,) (122)
3

---

Global sensitivity can be used with the Laplace and Gaussian distributions to form basic mechanisms. Let Lap(a) represent draw from the Laplace distribution with density f(x) 2a - /a and N [00, o²) represent the zero-mean Gaussian distribution with variance o². Each appearance of Lap(a) or (0, o²) represents an independent sample from the corresponding distribution.
Theorem (Laplace Mechanism [16). Given a privacy parameter 0, set Q of queries, and an imput dataset D. the mechanism M that returns the set of noisy answers {q(2) + (ap(A((()//)))))
satisfies e-differential privacy.
Theorem 2 (Gaussian Mechanism ( Given a privacy parameter > O, set Q of queries. and an input dataset D, the mechanism M that returns the set of noisy answers {q(D)
N (0,, (Q) (2p)))gee) satisfies p-zCDP.
All of these privacy definitions are postprocessing invariant 18 That is, let be an arbitrary algorithm. Then e M (i.e., the algorithm that outputs A(M(2)) )) satisfies (e, 6DDDP (resp., p-7CDP) if M satisfies (e, 5)D (resp., P-2CDP); in other words, the privacy parameters do not degrade.
They also have useful sequential composition properties. Let M M₁ be algorithms that satisfy pure differential privacy with corresponding parameters El:...,EE, Eg (resp., zCDP with corresponding privacy parameters Pl...., pk),, then the algorithm M that releases all of their outputs (i.e., releases (I))...... Mr (D)) satisties Σ, 4 differrent privacy 18 (resp., Σ, Pc-2CDP (
3 The Uncertainty Principle
The setting of d disjoint queries ç1....: Qd and their sum q, are some of the most important types of query sets. As discussed earlier, population counts in small geographic regions such as census blocks (examples of q:) are important for redistricting while population counts in larger regions such as counties (examples of q-) are used for federal and state funding formulas. Thus any tension between the q and q, can have significant impact on the entire U. S. population. While this just one example of a query set, almost every table produced in previous censuses is a query set with disjoint queries and their sums 40). Thus this is an important collection of queries to study.
3.1 Lower Bounds
We first remove some restrictions on M. While its input is a dataset, its output can be a positively weighted dataset collection of records in which each record has nonnegative weight w. A query with predicate & can be evaluated over weighted dataset by summing the weights of the records that satisfy vb. This simplifies our proofs and slightly increases generality, since normal microdata is special case of positively weighted data in which all weights are I (hence lower bounds for positively weighted data are also lower bounds for normal microdata). It also emphasizes the fact that these lower bounds arise specifically because negative query answers are disallowed. The lower bound is the following (see supplementary material for proofs).
.9 be a collection of disjoint queries and let q, be their sum. Let M be randomized algorithm whose input is a dataset and whose output is a positively weighted dataset. Suppose M guarantees that for each query qu and dataset D. (l(g((D) qi (M (2))) C and
Theorem 3. Let 91 ?9
Ellg. (D) 44(M (D)))² < D2 for some values C and D, where the expectation is only over the randomness in M.
If M satisfies c-differential privacy then for any k > O, we have 22C+4)) 2 k(d-1)
16C+8D+1k
which implies (a) if D2 < X/ē² for some constant X then C2 E E2 (d)), and (b) if C s x/e then D) E (())12).
If M satisfies (c. DDD then for any k > O. we have (++ (
4C+2D+k cxeC+22e 2
1/4, which implies (a) if D < 2/2 for some constant X then O2 E 2 (min( 3 (d), 1/2 log" 4)) ifC x/2 then either e O(6) or D2 (2)
If M satisfies p-zCDP, then the tradeoff function between C and D (which is more complex and omitted due to space constraints) implies: (a) if D2 < f/r some X. then C² e Ω (log(d)/P) p). and (b) if C < X/p.. then for any y (0, 1), we must have D2 ((dr/p))

---

Balcer and Vadhan [3] recently showed a statistical price of privacy-preservinge preserving release of the top-k counts in histogram. They proved an analogous (logg (d/k) (d/k)) penalty for point queries under e-DP (and also results for approximate DP). Interestingly. although they did not consider tradeoff's with the sum query (since its value was assumed to be public in their work), the results in our Theorem 3 (for c-DP and approximate DP, but not zCDP) can be proved using the result of their Theorem 7.2.
We also note that the tradeoff functions between C' and D in Theorem show a much stronger result than items (a) and (b) in Theorem 3 For example, they rule out the possibility that both C² and D can simultaneously be just slightly larger than ((1/e²). To understand and interpret Theorem 3 let us compare the Laplace and Gaussian mechanisms, which can produce negative query answers, hence are not equivalent to producing positively weighted datasets (hence not covered by Theorem 3
is easy to see that AI (q1....., qd; 9-) = and A2(1),... qd, q-) = v2. Hence, an algorithm M can add independent Lap(2/e) noise to each query to satisfy e-DP, and algorithm M2, can add independent (0, 1/p) noise to each query to satisfy p-zCDP. Thus M" achieves expected squared error of 8/e² for q. and each qi (i.e., C2 = D = 8/(²). Meanwhile p achieves 1/p expected squared error (C²- = D = 1/p). These expected error guarantees hold for all datasets D.
Theorem says that privacy-preeervvin algorithms M that are required to produce positively weighted datasets cannot guarantee the same low error- there are input datasets D for which the expected errors can be significantly larger. In the case of M that satisfy e-DP, if we want low error for the sum query (e.g.. D2 = O(1/22), matching the Laplace mechanism), on some datasets we may need to pay a log² (d) penalty for some point queries (i.e., there will be specific point queries with consistently large enror). On the other hand, if we want low error for the point queries (e.g., C = () then on some datasets we will pay a d² penalty on the sum query.
In the case of p-zCDP, the penalties are smaller. If we want to match the error of the Gaussian mechanism on the sum query, we may need to pay a penalty of log(d) on point queries; if we want O(1/p) expected squared error on each point query, we may need to pay a penalty of nearly d2 on q..
For approximate DP, the weakest privacy definition here, the degradation factor can be roughly log" (c/5) matter how large d is.
The lower bounds in Theorem 3 imply that if privacy-preserving microdata is generated by obtaining noisy measurement query answers (e.g.. with the Laplace or Gaussian mechanisms) and then postprocessing the noisy answers (e.g.. [28 24)). some of the measurement queries computed directly from the drvvac--rreeevvin microdata will have errors that are larger than their original noisy answers.
Remark 1.
Remark 2. All is not lost, however, as the proofs are based on packing arguments that show that these errors are unavoidable for some difficult datasets (but not all datasets are difficult). An example of diffficult dataset D under pure differential privacy is one for which exactly one of the query answers q1 (D"), )......
(x("") ".(""..((""" equals log(d)/e / while the other d - queries equal (clearly,
q- (2") log(d)/c). As mentioned earlier, the Laplace mechanism [18), which does not produce microdata, can achieve 8/2² per query error although many of the noisy query answers will be negative. However, the proof of Theorem 3 implies that no algorithm that produces privacy-protected microdata (and hence nonnegative query answers) can do as well on such a dataset. In fact, for this specific difficult dataset D', the large error described by Theorem 3 will either occur for q. or for that q whose answer on D' is (t.//. On the other hand, an easy dataset is one for which 41 (2), ... ())) are all large, since almost no effort is needed in ensuring that the privacy-protected query answers are nonnegative.
3.2 Upper Bounds
These lower bounds are nearly tight, as shown by the upper bounds in Theorem[4] The proofs construct postprocessing algorithms that first obtain noisy answers Q1...., ad, a, to the queries q1...., qd, q. postprocessing step converts the a; and a, into consistent noisy answers a', d'a. a' (i.e., they are nonnegative and Σ, a; d(). Weighted datasets are constructed from the latter quantities. To get weighted datasets with higher accuracy on point queries, the postprocessing ignores a, and sets a. max ). To obtain synthetic data with higher accuracy on the sum query, a, is set to a, and
5

---

the of are obtained by minimizing squared distance to the a, subject to the of being nonnegative and adding up to a.. The full proofs are the supplementary material.
Theorem (Upper bound for pure DP and zCDP). Let 9...... qa be a set of disjoint queries and let q- be their sum. Given privacy parameters >> 0 and > 0, there exist algorithmss Mc, M M M M2 s that output a positively weighted dataset and have the following properties:
1. Me satisfies cDPP, and for all D and i, E [((((M())) - -())))
v 2/e² and
E (M) -
1 222/2.
2. Mp satisfies p-zCDP, and for all D and i, E [[a((M - (D)))) - - 1/(2p) and E (M,()) - ( v d (2p).
3. M2 satisfies e-DP, and for all D and i, E ((((M) - - (D)))) E Ollgg (d)/²) and
E [{.( - (2)) E (1)/²)
4. MD satisfies p-zCDP, and for all D and 000 and - (
- E
E' [(g [ O(1/p)
5. Mys satisfies 5D and for all D and i, E (g - ) e 0loo"((16)/+ + 1) and E ( E 0(1/²), M2 satisfy c, 6.D..
- q.
Also note M. and
Note that Theorem 4 matches the lower bounds Theorem except for slight difference for zCDP, where Item of Theorem 4 has a d2 while the lower bound in Theorem 3 has in its place a d2" for any y arbitrarily close to
4 Algorithms
For tabular data, typically end-users are interested in multiple marginals of the data. Examples include the gender by age marginals the national, state, and county levels (for constructing age pyramids); the marginal on race at the national, state, county, tract, and block levels both for demographic research and for enforcement of voting rights; total populations in each state, county, etc. (for various funding formulas). Thus these query sets have many different point query/sum query collections embedded in them. Examples include: female population in a county (sum query) and number of females of each age in the county (point queries); or total Asian population (sum query) and Asian population in each county (point queries). Thus algorithms designed minimize the appearance of the uncertainty principle should not be designed for a single collection of sum/point queries; instead, they should support many counting queries.
To describe algorithms, it is helpful to view the dataset 2 as a vector x, where each element i corresponds possible record r,. Then x[i] is the number of times r; appears in D. The goal is version X whose entries are nonnegative real numbers, which can be converted to positively weighted dataset D (x[i] is the weight of record in D). In this setting, a counting query g is just a vector of 1s and Os with the same dimensionality as x, and the query answer is computed as the dot product x.
to produce a
The algorithms we present here (2 baselines and 2 proposed algorithms) are all based the idea of first computing noisy query answers and then postprocessing them to obtain x. This setup allows an organization to release both X and the noisy answers (for more statistically-orieneed end-users). Thus, given a set Q of counting queries, for each E Q, the data collector computes a noisy answer ag by adding noise with distribution Fg to the true answer and then must postprocess them create microdata
Fl We assume the data collector chooses the noise distributions to achieve their desired privacy definition (c.g., eDDP, p-zCDP).
3 "Although a data collector could add noise to a different set of queries and use them to infer the answers to E Q 43 29 42), it is the subsequent postprocessing step that would be more important in mitigating the uncertainty principle.

---

Baseline: NNLS Postprocessing. The first baseline we consider is the commonly used nonnegative least squares (NNLS), in which is produced as the solution the following optimization problem:
(ag 9.----x. x)2
f arg min
Σ
s.t. x(i] 2 0 for all
variance( Fg) BEQ
Baseline: Max Fitting Pastprocessing. The next baseline is an adaptation of bilevel optimization approach 322 that was originally used for optimization problems whose parameters are sensitive. The idea here is to find the positively weighted datasets whose query answers minimize the Loc distance to the noisy query answers, breaking ties using least squares error:
[0g q: x sld(F
dist min max qEQ
x 2 for all i
< arg min
Σ qeQ
(0g - q x)2 variance F.))
s.t. max 99--9.X1 std(F,) BEQ
S dist and x[] 2 20 for
Sequential Fitting Postprocessing. Since is provably not always possible to output microdata that fits the noisy answers well, we propose approach that prioritize queries. Thus the query set Q is partitioned by the user into query sets Q......Q Qu. We use the above NNLS approach to fit a vector X1 to the noisy answers of queries in Q1 (highest priority). We then fit X2 the noisy answers for queries in Q2 (next highest priority) subject to the constraints that X2 matches X1 on queries in Q1. Then we fit X3 using noisy answers to queries in Q3 while foreing X3 to match X2 on queries Q1 and Q2, and so on and return the final X at the end. The pseudocode is shown in Algorithm [] This algorithm is the one that matches the upper bounds in Theorem (referred as M when the noisy answers 0g use Laplace noise, and M% for Gaussian noise).
Algorithm 1: Sequential Fitting (Postprocessing)
Input: Query set Q, noisy answers Gg for q Q and noise distributions Fg for E Q. Input: QI,...: Qs: partition of Q based on query priority.
: X1 < arg ming EqEq, variance(F.)) S.I. x for all
(a)-
Fit Q1 for l = .2....,k h: do
X arg mins EnEq, ia-- xx
varsonce(F,)) s.t. x(1 2 0 for all and q. q- 8e-1 for all q E Fit
Fit Fit UQQ
8 Return: X²
The constrained optimizations max fitting and sequential fitting are difficult for quadratic program optimizers, often resulting in numerical errors, slow convergence, and infeasibility errors (due to occasional insufficient solution quality in earlier stages of the multistage optimization). They require significant engineering effort, tuning of slack parameters (slightly relaxing equality and inequality constraints) and optimizer-specific parameters. So, an ideal solution would also avoid constraints other than nonnegativity for point queries. This is rationale for our next method.
Remark.
Re Weighted Fitting Postprocessing. This method (shown in Algorithm 2 avoids constraints as much possible in eventual NNLS solve (Line 14 but is limited to query sets of the form Q U Q.. where the queries inside each Q; are disjoint and have the same noise distribution. One example is when Q is a collection of marginal queries (c.g., Q1 = marginal on age, Q2 = marginal on age by race, Q3 marginal on gender by race), which are arguably the most important types of queries. Within each Q. the algorithm tries to find a cutoff value so that queries with noisy answers above are likely to have true value that non-zero (iines(5l)) The idea that if n the number of queries below the threshold, and if they truly had value U, then their largest noisy value (i.e., the max of ni O-mean Laplace or Gaussian random variables) should not be near the cutoff with high probability (controlled by the confidence parameter 7). The "low" queries are the ones with noisy answers below the cutoff. The algorithm uses the existing noisy answers estimate the sum of these "low" queries (Lines [I 12 and adds that "low query sum" (Line 13) to the nonnegative
7

---

least squares optimization while downweighting the individual low queries (Line ② the downweight depends on the extreme value distribution of the max of n, O-mean Laplace or Gaussian random variables, Line 77. To avoid double counting, both places where a "low" query is used (individually and as part of sum) have their weights cut in half. Note the algorithm only uses existing noisy answers and has no access to the true data.
Algorithm 2:
Re ReWeighted Fitting (Postprocessing)
Input:
Query set Q U Q Within a Qt the queries are disjoint. F; is the noise distribution of each query in Q. Given noisy answers 0g for q E Q that satisfy the chosen privacy definition.
2
Input: Confidence parameter 7 close to (e.g.. 0.99, the setting used in experiments) S
+- for i 1, ..... k do
4
((1), ((2):-.. are the given noisy answers (to queries in Q:) arranged in sorted order j <- smallest s.t. s.t. P(max(j fresh random variable with distribution F:) 2 "())s
5
cutoff + O(j)).
7
downweiggt <- median of distribution of max of j random variables sampled from F; For each query q E Qi whose noisy answer ag is 2 cutoff, add (q. ag. 1/taa///)))))))a (F:)) to S. For each query q E Q: whose Og is cutof add (g, lgg 2evar ( (i)doowwwwi)))h to S.
10
n. + number of queries selected in Line 9 (i.e., their noisy answers were < cutof] f)
11
at f sum of queries selected in Line
12
at f sum of their existing noisy answers
13
Add (gt, ato 2an(var(F.) to S
14 f- arg ming La w (g'( - d²)² s.t., x[1] 2 0 for all
15 Return: x
Experiments
To make our code fully open source, we wrote it in Julia [5] and after trying several open-source optimizers, we settled on COSMO (1I). We created a collection of benchmark datasets that were small enough to permit running the postprocessing algorithms thousands of times on each dataset (to estimate expected errors) but large enough to demonstrate the uncertainty principle. The full benchmark of 15 real datasets and 16 synthetic datasets is described in the supplementary material Here we present results for an interesting subset. The only synthetic dataset discussed here, called Level00-2d 2d, is a 10 10 histogram where one element is large (i.e., 10,000) and the others are O. The other 15 datasets we discuss here were taken from the 2016 ACS Public-Use Microdata Sample [39]. Each represents a 9 x 24 "race by Hispanic origin" histogram from Public-Use Microdata Areas that were considered outliers in their states in terms of racial composition.
For these datasets, applied the Laplace mechanism with 0.5 to answer the sum query, both 1-way marginal queries, and identity queries (for each cell, how many people are in it). This is also the priority order used by Sequential Fitting. Error results for the marginals, other privacy parameters and zCDP results can be found in the supplementary material. We ran the Laplace mechanism using different postprocessing strategies (described in Section 4 1 1,000 times for each dataset estimate expected squared error of each query. We added an ordinary least squares (OLS) optimization for comparison purposes (OLS is NNLS without nonnegativity constraints). OLS is free from the uncertainty principle because it does not produce positively weighted microdata. Thus, to minimize the effect of the uncertainty principle, the other postprocessing methods should try achieve errors that are not much worse than OLS. We note that the multi-stage optimization in Max and Sequential fitting are generally very difficult for optimization software, so we only kept those runs in which the optimizer succeeded (thus results for Max and Sequential Fitting are slightly optimistically biased).
In Table I we show the squared error of these postprocessing methods for the sum query. The NNLS and MaxFitting baselines perform poorly for this query, with errors typically 4-5x those of the OLS method (which is close to the variance of the original noisy answer to the sum query). Meanwhile
"eee http://///hh..oooccccccc///////t
for the code and data.

---

Dataset Nickname
Dataset
OLS
NNLS
MaxFit
Seq
ReWeight
201
Level00-2d
101.3
461.9
533.9
149.2
108.5
202
PUMA010130
107.2
547.2
500.3
106.7
112.5
203
PUMA0800803
107.2
446.1
571.7
120.3
107.2
204
PUMA
107.2
408.1
426.3
120.8
109.8
205
PUMA1703522
107.2
435.3
426.3
134.9
110.9
206
PUMA170352
107.2
584.0
677.4
111.4
108.1
207
PUMA 700
107.2
395.1
443.6
119.1
110.4
208
PUMA2401004
107.2
369.3
329.0
109.6
107.5
209
PUMA2602702
107.2
467.8
472.0
146.0
109.2
D DIO
PUMA2801 100
107.2
543.7
558.2
117.8
110.8
211
PUMA2901 901
107.2
485.2
464.4
126.5
110.8
112
PUMA3200405
107.2
329.1
301.0
122.9
108.4
213
PUMA3603710
107.2
300.3
293.3
85.7
108.8
214
PUMA3604010
107.2
399.9
386.5
129.8
111.3
215
PUMA5101301
107.2
396.1
369.5
139.2
107.2
Q16
PUMA5151255
107.2
330.7
280.3
139.1
107.8
Table I: Squared Error for Sum Query (overall 0.5))
OLS
NNLS
MaxFit
Seq
ReWeight
Data
Total
Max
Total
Max
Total
Max
Total
Max
Total
Max
201
10516.5
124.0
344.2
147.4
443.7
173.1
437.3
283.6
159.2
78.4
D02
23906.2
142.9
809.0
135.6
910.7
144.6
782.9
179.7
731.3
209.8
203
23906.2
142.9
1179.8
107.5
1235.3
125.4
1171.7
189.8
1123.8
141.9
204
23906.2
142.9
1313.0
111.9
1385.5
142.3
1049.1
126.3
1264.4
136.0
D05
23906.2
142.9
1243.8
105.3
1257.2
96.7
1019.1
114.3
1285.7
160.5
D06
23906.2
142.9
562.2
94.9
599.0
72.1
429.9
112.9
409.8
78.8
207
23906.2
142.9
1516.1
115.9
1665.9
129.7
1312.1
156.9
1617.1
205.0
D08
23906.2
142.9
1954.4
130.0
1971.8
147.8
1983.4
311.3
1760.1
168.9
D09
23906.2
142.9
977.2
100.0
956.4
109.4
843.4
121.7
930.1
156.2
D10
23906.2
142.9
686.9
97.5
705.7
79.0
534.2
92.7
516.0
78.7
Q11
23906.2
142.9
944.4
100.4
919.2
103.2
809.4
131.6
888.2
138.2
112
23906.2
142.9
2189.2
119.6
2191.5
134.7
1918.5
142.3
2336.1
259.1
D13
23906.2
142.9
2884.1
119.2
3088.6
149.1
2484.2
140.7
2870.4
166.1
D14
23906.2
142.9
1432.5
105.9
1442.3
120.6
1262.1
122.7
1448.6
194.0
D15
23906.2
142.9
1474.7
108.3
1498.6
101.8
1394.5
203.4
1392.9
153.2
D16
23906.2
142.9
2239.7
130.3
2274.1
124.3
2079.0
178.5
2123.0
172.8
Table 2: Squared Errors Id Query (overall c= 0.5).
Sequential and ReWeighted fitting perform much better. Standard errors were roughly 2-6% of the reported metries (omitted for space, but shown the supplementary materials).
For Table 2 we examine the expected errors of each cell query (i.e., qi is the number of people in cell i). We find the cell with the largest expected error and report it (the "Max" column). We also find the total squared error of the cell queries and report them in the "Total" column. Again, the standard errors are roughly 2-6% of the reported metrics, except that they are sometimes higher for Max and Sequential fitting since averages were only computing on the subset of runs for which the optimizer did fail.
Generally, NNLS performed slightly better in terms of the maximum expected error compared to ReWeight, although their total errors are comparable and WeWeight significantly outperforms NNLS on the sum query.
Overall, these experiments and our supplementary material show that both ReWeight and Sequential fitting (though not perfect) avoid incidents where there are extremely high error (unlike NNLS and Max Fitting for sum queries), and this is important in practice. ReWeight and Sequential fitting have similar performance. Reiei is faster while Sequential needs significant tuning of optimizers in order to succeed. However, one advantage of Sequential is its algorithmic transparency it can

---

directly prioritize queries for the tradeoffs caused by the uncertainty principle (in our experiments, the sum query had highest priority for Sequential Fitting).
6 Related Work
The requirement to produce microdata is an example of consistency in Privacy-preservy query answering. variety of work 25 35 28
30 27 24 has shown that creation of a privacy- preserving data synopsis from which all queries are answered can improve query accuracy under variety of metrics such as maximum simultaneous error and total error. However, it is known that the production of Srivacy-preserving microdata comes at the expense of increased computational cost
17 38]. For example, under standard complexity assumptions [38], there no polynomial algorithm for generating privacy-protected synthetic data whose two-way marginals are all accurate.
Aside from the computational price, Balcer and Vadhan [ also recently showed a statistical price of
synthetic data. They considered releasing different kinds of criaac--rootcctd representations of nonnegative noisy histograms (for example, releasing the top-k noisy cells under e-DP had a log" (d/k) penalty term for squared error), but assumed the value of the sum query was publicly known in their work. Our constructions are based on their proof techniques (see discussion after Theorem 3).
7 Conclusions, Future Work, and Broader Impact
Public-use data have many different end-users, so a single aggregated performance measure, such as total error across all queries, is not a reliable measure of data quality. The accuracy of each query is important, which implies multiple conflicting quality criteria for public-use data. Thus an important direction for future work to identify all tradeoff's srivacy-preseringg microdata as well as algorithms with provable guarantees on instance-optimality (i.e., improve performance on datasets that do not trigger the uncertainty principles).
Broader Impact
The uncertainty principle presented in this paper (as well as the cost of microdata results in 33 along with the known computational price of generating microdata suggests that organizations should also consider alternative formats for their privacy-protectoe be avoided by releasing noisy query answers that are allowed to be negative by producing weighted datasets that can feature negative weights (however, adding a sparsity requirement could re-introduce systematic errors (3). Such alternative formats may also require educating and providing training microdata,
data products. The uncertainty principle can
materials to end-use uusur.es. If an organization nevertheless decides to produce then microdata- geaaatannnnennggggg algorithms should be designed postprocessing algorithms that convert unbiased noisy measurements into microdata (so that the "statistics-friendl" noisy measurements can also be released and studied by data scientists). Further research into such postprocessing algorithms needed to mitigate the effects the uncertainty principle.
Acknowledgments and Disclosure of Funding
We thank Salil Vadhan for helpful discussions that allowed to sharpen the lower bound results. Affiliations are provided solely for the purpose of identification. All work was performed under the supervision of the U.S. Census Bureau as part of the authors' employment product. The views and opinions in this article are those of the authors and do not represent the policy or official position of the U.S. Government, the U.S. Department of Commerce, the U.S. Census Bureau, the U.S. Department of Homeland Security, Knexus, or Tumult Labs.
contractual work
Competing interests: None.
Additional revenues related to this work: None.
10

---

References
[1] John M. Abowd. The U.S. Census Bureau adopts differential privacy. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, KDD 2018, pages 2867-2867, New York, NY, USA, 2018. ACM. /ottps:/ddl. acm. org //g//oi/10
1145/321988 91119 3226070
[2] Shahab Asoodeh, Jiachun Liao, Flavio Calmon, Oliver Kosut, and Lalitha Sankar. A better bound gives hundred rounds: Enhanced privacy guarantees via f-divergences. In 2020 IEEE International Symposium on Information Theory (ISIT), 2020.
[3] Victor Balcer and Salil Vadhan. Differential privacy on finite computers. Journal of Privacy and Confidentiality, 9(2), Sep. 2019.
[4] Boaz Barak, Kamalika Chaudhuri, Cynthia Dwork, Satyen Kale, Frank McSherry, and Kunal Talwar. Privacy, accuracy and consistency too: A holistic solution to contingency table release. In Proceedings of the ACM SIGACT-SIGMOD-SIGAN Symposium on Principles of Database Systems (PODS), 2007.
[5] Jeff Bezanson, Alan Edelman, Stefan Karpinski, and Viral Shah. Julia: A fresh approach to numerical computing. SIAM review, 59(1):65-98, 2017.
[6] Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnes, and Bernhard Seefeld. Prochlo: Strong privacy for analytics in the crowd. In Proceedings of the 26th Symposium on Operating Systems Principles, SOSP 17., pages 441-459, New York, NY, USA, 2017. ACM.
[7] Avrim Blum, Katrina Ligett, and Aaron Roth, A learning theory approach to non-interactive database privacy. In Proceedings of the Fortieth Annual ACM Symposium Theory of Comput- ing. 2008
[8] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. Theory of Cryptography, 2016.
[9] Clément L. Canonne, Gautam Kamath, and Thomas Steinke. The discrete gaussian for differen- tial privacy. In NeurlPS, 2020.
[10] U.S. Census Bureau. LEHD ingiin-Destination Employment Statisties (2002-2018) [computer file], 2021. U.S. Census Bureau, Longitudinal-Emploon Household Dynamics Program [dis- tributor], accessed on October 11, 2021 at attttss://onthema ces. census, gov LODES 7.5 [version].
[11] Graham Cormode, Cecilia Procopiuc, Divesh Srivastava, Entong Shen, and Ting Yu. Differen- tially private spatial decompositions. In ICDE, 2012.
[12] Thomas M. Cover and Joy A. Thomas. Elements of Information Theory (Wiley Series in Telecommunication and Signal Processing). Vitey-Interscceece, USA, 2006.
[13] Bolin Ding, Janardhan Kulkarni,, and Sergey Yekhanin. Collecting telemetry data privately. In Proceedings of the 3 International Conference on Neural Information Processing Systems, NIPS' 17, pages 3574-3583, USA, 2017. Curran Associates Inc.
[14] Bolin Ding, Marianne Winslett, Jiawei Han, and Zhenhui Li. Differentially private data cubes: Optimizing noise sources and consistency. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, 2011.
[15] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Serge Vaudenay, editor, Advances in Cryptology EUROCRYPT 2006, 2006.
[16] 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.
11

---

[17] Cynthia Dwork, Aleksandar Nikolov, and Kunal Talwar. Efficient algorithms for privately releasing marginals via convex relaxations. Discrete Comput. Geom., 53(3):650-673, 2015.
[18] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy, Founda- tions and Trends in Theoretical Computer Science, 9(3 ((3-4):2112))
2014.
[19] Ülfar Frlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy-preserving ordinal response. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communicattion Security, CCS 14. pages 1054-1067, New York, NY, USA, 2014. ACM.
[20] Simson L. Garfinkel, John M. Abowd, and Sarah Powazek. Issues encountered deploying differential privacy. In Proceedings of the 2018 Workshop on Privacy in the Electronic Society, 2018.
[21] Michael Garstka, Mark Cannon, and Paul Goulart. COSMO: A conic operator splitting method for large convex problems. In European Control Conference, 2019.
[22] Arpita Ghosh, Tim Roughgarden, and Mukund Sundararajan. Universally maximiin privacy mechanisms. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, 2009.
[23] Samuel Haney, Ashwin Machanavajjhala, John M. Abowd, Matthew Graham, Mark Kutzbach, and Lars Vilhuber. Utility cost of formal privacy for releasing national employer-employee statistics. In Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD '17, pages
New York, NY, USA, 2017. ACM.
[24] Moritz Hardt, Katrina Ligett, and Frank McSherry. A simple and practical algorithm for differentially private data release. In NIPS, 2012.
[25] Michael Hay, Vibhor Rastogi, Gerome Miklau, and Dan Suciu. Boosting the accuracy of differentially private histograms through consistency. Proc. VLDB Endow, 311-22:102--1033 September 2010.
[26] Noah Johnson, Joseph P Near, and Dawn Song. Towards practical differential privacy for sql queries. Proceedings of the VLDB Endowment, 11(5):526- 539, 2018.
[27] Jaewoo Lee, Yue Wang, and Daniel Kifer. Maximum likelihood postprocessing for differential privacy under consistency constraints. In Proceedings of the 21th ACM SIGKDD International Conference Knowledge Discovery and Data Mining (KDD), 2015.
[28] Chao Li, Michael Hay, Vibhor Rastogi, Gerome Miklau, and Andrew McGregor. Optimizing linear counting queries under differential privacy. In PODS, 2010.
[29] Chao Li, Michael Hay, Vibhor Rastogi, Gerome Miklau, and Andrew McGregor. Optimizing linear counting queries under differential privacy. In Proceedings of the Twenty-Ninth ACM SIGMOD-STGACT-SIGARR
Symposium on Principles of Dutabase Systems, 2010.
[30] Chao Li, Gerome Miklau, Michael Hay, Andrew Megregor, and Vibhor Rastogi. The matrix mechanism: Optimizing línear counting queries under differential privacy. The VLDB Journal, 24(6):757-781, 2015.
[31] A. Machanavajhala, D. Kifer, J. Abowd, J. Gehrke, and L. Vilhuber. Privacy: Theory meets practice on the map. In 2008 IEEE 24th International Conference on Data Engineering, pages 277-286, Piscataway, NJ, USA, April 2008. IEEE.
[32] T. W. Mak, Ferdinando Fioretto, and P. V. Hentenryck. Bilevel optimization for differentially private optimization. ArXiv, abs/2001 .09508, 2020.
[33] Solomon Messing, Christina DeGregorio, Bennett Hillenbrand, Gary King, Saurav Mahanti, Zagreb Mukerjee, Chaya Nayak, Nate Persily, Bogdan State, and Arjun Wilkins. Facebook Privacy-Protected Full URLs Data Set, 2020.
12

---

[34] National Academies of Sciences, Engineering, and Medicine. Chapter 11: Census bureau's s responses and own analyses of 2010 demonstration data products. In Proceedings of the 2020 CNSTAT Workhop on Census Data Products: Data Needs and Privacy Considerations. The National Academies Press, 2020.
[35] Wahbeh Qardaji, Weining Yang, and Ninghui Li. Understanding hierarchical methods for differentially private histograms. 2013.
[36] D. Ridgeway, M. Theofanos, T. Manley, and C. Task. Challenge Design and Lessons Learned from the 2018 Differential Privacy Challenges, National Institute of Standards and Technology Technical Note. https://doi . org/10. 60w.:....2..SSTT.. TN 2151 2021.
[37] Apple Differential Privacy Team. Learning with privacy scale, 2017.
[38]
Jonathan Ullman and Salil Vadhan. Peps and the hardness of generating private synthetic data. In Proceedings of the 8th Conference on Theory of Cryptography, TCC' 11, page 400-416, Berlin, Heidelberg. 2011 Springer-Verte Verlag.-Veellg.
[39] U.S. Census Bureau. 2016 american community surve public use microdata samples (pums). 2016 html
https://wwv. census wtwp:///gow//ooggaaaauuueeeeeee
[40] U.S. Census Bureau. Decennial census: 2010 summary files. https: http:/wwwwennun. gov/
mp/ wwwp/cat//eecemiaaa_cnnusu _2100/
[41] Salil Vadhan. The Complexity of Differential Privacy, pages 347-450, Springer International Publishing. 2017.
[42] Yingtai Xiao, Zeyu Ding, Yuxin Wang, Danfeng Zhang, and Daniel Kifer. Optimizing fitness- for-use of differentially private linear queries. Proc. VLDB Endow. 14(10), 2021.
[43] Ganzhao Yuan, Yin Yang, Zhenjie Zhang, and Zhifeng Hao. Convex optimization for linear query processing under approximate diffcrential privacy. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016.
13


Reviews:
[{"review_id": "qKqjlebJL9u", "reviewer": "Reviewer_epzC", "summary": "The paper presents results for the problem of a mismatch between accuracy of answers to queries on the data. In particular, it considers two types of queries: d microdata queries and a query whose result corresponds to a sum of answers to microdata queries. It observes that there is a mismatch between the accuracy if one was to first return a privacy-preserving answer to microdata queries and then construct an answer to the sum query and vice-versa. The paper determines lower bounds of the accuracy relationship between answers to thes type of queries. It also presents upper bounds (it is not quite clear if algorithms presented later is the basis of these bounds). Finally it also evaluates proposed and baseline algorithms on a few datasets computing the error.", "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": "The paper is well written and is comprehensible on its contributions.\nI was not clear if considering only mechanisms that return \"positively weighed datasets\" is a limitation or a generalisable way of viewing DP mechanisms or an artifact of the proof.\nReference to sub queries as microdata queries seems confusing as microdata usually refers to individual level data however in this paper it seems to be count data. If it is the former, it is not clear why comparison with local DP is not made.\nBaseline algorithms seem to be adhoc and not consider works that also use optimization to combine subqueries in a best possible way. For example, works such as matrix mechanism in \"Optimizing error of high-dimensional statistical queries under differential privacy\" 2018 by McKenna et al. It would be good to see comparison of upper bounds in the paper and in experiments.\n\nMinor:\nThough I only found arxiv version of [3], I could not find \"uncertainty principle\" explicitly defined.\n\nAfter author response:\nThank you for addressing my questions and clarifying some misunderstandings. I updated my score accordingly.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "mrYxB-AGPTr", "reviewer": "Reviewer_ecPK", "summary": "The authors investigate a synthetic data generation scheme that on which results of counting queries are consistent with (privacy-perturbed) results from the original data over different levels of query granularity, i.e., where the result of some queries may be obtained as the sum of a set of more granular queries. The assumed generative process evaluates a given set of queries on the original data under privacy constraints. It then constructs synthetic data by means of solving an optimization problem that minimizes a suitable error term between query responses on synthetic data and the perturbed results from the original data. \n\nThe authors provide theoretical results in form of lower and upper bounds which show there is a trade-off in optimizing on different granularity levels that is inherent to this process (and depends on the number of queries on finer granularity levels). Specifically, they show that it is impossible to achieve constant accuracy/error for different levels of granularity.\n\nThe authors propose two new approaches for solving the optimization problem in the generative process. The first allows the user to prioritise certain query sets over others, while the second dynamically discounts query results based on an estimate of whether the (unperturbed) value is (close to) 0, thus allocating more importance to accurately representing non-zero results in the generated data.\n\nFinally, they propose a set of benchmark data sets and evaluate their algorithms and compare to common baselines.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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:\nThe paper extends recent results in [3] to a more general setting. While the discussion of related work is rather short, it suggests that this has not yet been tackled in this form in the literature (and I am not aware of any such work). While the overall phenomenon the paper discusses is not new (and, arguably, not surprising), the theoretical bounds found by the authors are. This contribution is maybe a bit marginal but overall interesting.\nAdditionally, the paper also proposes new algorithms for the optimisation step of the noisy-query-based data generation process that were empirically found to reduce error over off-the-shelf methods, but no theoretical results on their performance is given. The final contribution are data sets for evaluation, but they are not discussed in great detail in the main body of the paper. In sum, I think these might just make for sufficient contributions to warrant considering acceptance of the paper.\n\nQuality:\nThe paper is overall well written and methodically sane. I have not found any obvious flaws. (I have checked the proof for the pure DP case of Theorem 3, but was unfortunately unable to delve into the remaining proofs in detail.)\n\nClarity:\nThe paper is overall mostly clear. There are some paragraphs that are a bit dense and might require a second pass of reading to be fully understood as they introduce a lot of material at once. Overall this is not a major impediment to understanding the paper as a whole but may have impact how much can be taken away from certain paragraphs (the discussion of Alg 2. is maybe the most troublesome in this respect).\n\nPersonally, I think the switch to weighted data sets the way it is presented decreases clarity somewhat by adding (unnecessary?) complexity. Sticking to unweighted data sets for the main results of Sec 3. would probably have been easier to follow (and it would still be possible to then say this also holds for the more general case of weighted data sets).\n\n\nSignificance:\nThe paper tackles an important question for widespread adoption of privacy-preserving sharing of data. The theoretical results demonstrate fundamental limitations to accuracy of such data in general purpose use that both data owners and analysts using privacy-preserving synthetic data must be aware of. These are important findings to the entire machine learning / statistics community, for which privacy becomes a larger and larger concern.\nThe experimental results on variations of the generative process suggest that off-the-shelf optimization methods might not be optimal in this setting and special-purpose algorithms tailored to prioritise specific queries decrease overall error (which is maybe not a totally new insight).\n\nSome open questions:\n- It is not entirely clear to me why the process using OLS is not subject to the trade-off bounds, and probably related, why is the OLS output constant over D02-D16 (for both sum and identity queries)?\n- You state \"There are datasets for which the error penalties do not exist.\": Do you have any insights in what characteristics of a data set lead to the presence of the error penalties?\n- Could you clarify why the proof of the pure DP case of Th. 3 considers data sets that are not neighbors by your definition but \"differ by the addition/removal\" of at least $2(\\alpha C +k)$ records? How exactly does this provide DP bounds for the neighboring relation you consider?\n\nMinor comments:\n- line 119: \"then the algorithm that M that releases\": superfluous \"that\" after \"then the algorithm\"\n- Alg 2: line 1: \"Query set $Q=\\cup_{i=1}^k$\" : missing \"$Q_i$\" ? ; line 8: \"cutoff\" not italicized; line 8,9: $a_q$ inside the tuple?\n\nUpdate:\n\nI thank the authors for their response to the questions I raised during my initial review. My first two questions stand fully addressed.\n\nHowever, I feel my concerns about the usage of far-apart data sets in the proof of theorem 3 have not been entirely addressed. While I can see the gist of the argument (\"we can easily make use of group privacy property for data sets with distance > 1\"), I am not entirely convinced this works in contraposition here, i.e., that the proof then generalises to data sets with smaller distances. I must however admit that I am not familiar with this proof technique.\n\nUpon revisiting the work, another point is now concerning to me: The assumption for the synthetic data release mechanism seems to be that all point queries as well as the sum query require the same amount of perturbation to achieve a certain ε. However, since the the point queries operate on disjoint subsets of the data, we know from work on privacy amplification through subsampling that the perturbation applied to point queries should be much smaller than for the sum query to achieve the same level of ε. According to some back-of-the-envelope calculations, this might resolve the utility problem at hand.\n\nThis is not at all discussed in the paper, which essentially considers a set of point queries whose privacy assumptions imply that all subsets may differ by one element simultaneously, but where aggregating their perturbed outputs should match that of a query over the whole data for which the assumption is that only a single record over the entire data set may differ. The resulting conflict between utilities on the different levels is then not really surprising.\n\nNow, I still believe that the analysis of the paper is overall valid and interesting for the assumed technique. The technique itself seems to have been taken from previous literature/practice. I strongly feel a paper that analyses a trade-off in point versus sum queries must take this issue into account if it makes a claim about this trade-off being a general property of privacy-perserving synthetic data. The current paper would currently only be an evaluation/criticism valid for that particular synthetisation technique.\n\nI can therefore no longer recommend the paper for acceptance in its current form and have reduced my score by a point to give the authors a chance to improve and strengthen this promising work, for which I wish them all the best for the future.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors point out the limitations of their analysis and the proposed algorithms clearly.\n\nThere appears to be no direct discussion about potential negative societal impact. However, the very objective of the paper is, in a sense, to call to attention and outline potential solutions to avoid a (subtle?) flaw in privacy-preserving methods; Given that, I don't think there are negative societal impacts that would merit much discussion in the scope of this paper in the first place.", "review_text": "", "extra_scores": {"ethical_concerns": "I have not noticed ethical issues with the paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "aMZVW37VcQ_", "reviewer": "Reviewer_WJWj", "summary": "The paper addressed the following problem. In an earlier report of reference [30] that studied the Census Bureau’s data, it was shown that the query error from the privacy-protected microdata was much larger than the measurement query error. The paper studied this “anomaly” and shows that it is unavoidable for privacy-protected microdata.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "* Strength:\nThis paper provides a theoretical analysis of the tradeoff between accuracy on populations and accuracy on sub-populations.\n\n* Weakness:\n- the paper is not well-written. There are many undefined terms and notations. \n- the keyword microdata has to be rigorously defined\n- the theoretical results are somewhat incremental, given earlier work, e.g., the tradeoff analyses in [3] \n- It is unclear how tight the derived lower bounds are. The practical implication of these bounds needs to be discussed.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "6rCFBAWG0GE", "reviewer": "Reviewer_dx3d", "summary": "This paper studies the problem of the accuracy of privacy preserving microdata. It presents bounds on the tradeoff between the accuracy of the population and the accuracy of the sub-populations. It also presents some algorithms that mitigate the effects of what they call the uncertainty principle and benchmark datasets to be used for studying this problem further. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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: the paper presents an uncertainty principle, along with bounds and algorithms that may help mitigate the effects of this uncertainty. The results are based upon previous works, however the results are valuable and novel. The paper also properly cites previous work and discusses differences very clearly.\n\nQuality: The work is technically sound and the claims are well supported. The algorithms presented are not theoretically proven but this is discussed by the authors. Despite that, the presented work can be a good stepping stone for this line of work. The authors discuss truthfully the limitations of their work and give enough credit to the literature this work is based upon.\n\nClarity: The paper is well organised and clearly written with minor typos and things that can be better clarified, such as,\n\n- In section 3.1, 'Theorem 3 says that ... produce positively weighed errors', should be 'weighted'.\n- In the beginning of section 3.2, it is good to maybe discuss a bit further how the bounds in theorem 4 shows the tightness of the bounds in theorem 3.\n- In theorem 4, 'Given privacy parameters ... There', the 'T' should not be capitalised.\n\nSignificance: The results of the paper are important and useful, and it will lead to more work on the topic. This problem is a challenging problem and this paper provides good results in order to work on it.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have discussed as thoroughly as possible the limitations of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper analyses patterns of additional errors inherent in creating privacy-preserving microdata. This addresses an important and timely issue, as such methods are being adopted in high-profile applications such as US Census 2020. The paper presents a careful theoretical analysis with both upper and lower bounds.

The reviews of the paper are divided. Two reviewers appreciate the importance of the paper and recommend acceptance, while two recommend rejection mainly based on concerns of the applicability of the results: they are concerned about communicating the implications of the results (seemingly answered in author response) and whether the results are specific to the mechanism analysed and could be circumvented by using a different mechanism.

Because of the high significance and potential impact of the work, I tend to favour acceptance.

If the paper is accepted, I would encourage the authors to add discussion on the assumptions on the mechanisms made and their significance on the conclusions, if applicable.
Decision: Accept (Poster)