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": "qJbosxscd8w", "reviewer": "Reviewer_bo89", "summary": "\nThe authors study the problem of quantifying the statistical price of\nreleasing sum queries (for a population) versus point queries (for sub-populations).\nMicrodata (e.g., used extensively by the U.S. Census Bureau and associated governmental\nagencies) is certainly very valuable. But naively releasing these microdata could lead to\nprivacy violations. So we can resort to differentially private (DP) methods for microdata\nrelease.\nFor DP sum queries, one might incur an additional $O(d^2)$ multiplicative factor in additive\nerror loss while a $O(\\log^2 d)$ factor might be incurred in the point queries setting.\n\nThe goal of the paper, it seems, is to create a collection of benchmark datasets and\nmitigation strategies to alleviate (\"inherent and unavoidable\") issues with DP microdata release.\n\nThe uncertainty principle presented suggests that microdata-generating algorithms should be\ndesigned as postprocessing algorithms that transform (unbiased) noisy measurements into microdata.\n\nThrough an extensive set of experiments (see Table 1, 2), the authors validate their principles.", "questions": "", "limitations": "", "rating": 8, "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": "It is known publicly that the U.S. Census Bureau release of microdata had significant\nanomalies. The system first produced measurements via DP noisy quer answers and then\nattempted to match (via post-processing) the noisy measurements to certain microdata.\n\nThe authors introduce an uncertainty principle that trades off error between accuracy on\npopulations and accuracy on sub-populations.\n\nThe Uncertainty Principle\n-------------------------\n\nThere are two criterion for squared error they consider.\nThe first is the per-query expected error (let's call PQ)\nwhich is the maximum over all queries of the expected\nerror and the second is the sum-query (let's call SQ)\nexpected error which is the sum over all the\nqueries. The authors posit that to bound both PQ and SQ, one has to choose between a\n$O(\\log^2 d)$ penalty term for point queries and a $O(d^2)$ penalty term for sum queries.\n\nThe authors note that their bounds (upper and lower bounds) affect some, *but not all*,\ndatasets.\n\nAlgorithms\n----------\n\nThe authors present two baselines and two proposed algorithms all based on first computing\nnoisy query answers and then postprocessing.\n\nI'm wandering what happens with the baselines when\nvariance/std of $F_q$ is close to 0? It seems the optimization problem becomes infeasible. [response acknowledged]\n\nMinor Comments\n--------------\n- Line 44: \"... of Black of African Americans ...\" -> \"... of Black or African Americans ...\"\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors adequately consider the limitations and broader impact of their work. See Section 7 in their paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "gqyq9lkQm2t", "reviewer": "Reviewer_4cAR", "summary": "The paper studies the problem of releasing count queries on a population along with counts from sub-populations. The first result of the paper is an “uncertainty principle“, a lower bound stating that if the mechanism is private (DP, approx, or zCDP) then either the error in at least one of on the subpopulations is large, or the error on the population is large. Then, in Theorem 5 the authors prove that there are private algorithms that nearly match the lower bounds. Finally, the authors provide new post processing algorithms for releasing microdata and evaluate them on 16 datasets with positive results.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem that the authors study is definitely of importance, the Census being a great example. The paper is easy to read and follow. I am unsure about how original the proof of Theorem 3 is and I think the authors should discuss a sketch of the proofs or discuss the novelty in the argument (if any). The proof of theorem 4 seems nontrivial and the postprocessing algorithms in section 5 seem original, specially Algorithm 2.\nThe experiments section shows that the proposed algorithms perform well in at least 2 of the proposed datasets, I think the section could be considerably improved by summarizing what were the results in the other 14 datasets.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "PFceW2FdRzh", "reviewer": "Reviewer_eGa2", "summary": "The paper studies the problem of answering disjoint count queries under differential privacy (DP), and presents lower bound of query errors under three variants of DP.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "My main concern of the paper is that it ignores two prior studies that present more general and significant results:\n\n1. Irit Dinur, Kobbi Nissim: Revealing information while preserving privacy. PODS 2003: 202-210. \n\nThe query error bounds in this paper are applicable to any count queries and any reasonable notion of privacy.\n\n2. Avrim Blum, Katrina Ligett, Aaron Roth: A learning theory approach to noninteractive database privacy. J. ACM 60(2): 12:1-12:25 (2013)\n\nThe paper shows that under differential privacy, the query error bounds are decided by the VC dimension of the query set.\n\nCompared with the above studies, the current paper is much narrower in scope, as it only considers disjoint queries under differential privacy. In addition, some of the theoretical results presented in the paper (e.g., the case for \\epsilon-differential privacy in Theorem 3) seem to be corollaries of the results in the J. ACM 2013 paper. Therefore, the contribution of the current paper is rather limited.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "H_3RSWiw5EJ", "reviewer": "Reviewer_NcCk", "summary": "The authors consider two different ways of answering counting queries in a differentially private manner; answering the queries directly through a querying system or giving synthetic microdata. They present an \"uncertainty principle\" stating that, for some data sets and for a particular accuracy metric, the accuracy of differentially private microdata \nmust suffer either on \"sum queries\" or \"point queries\" relative to the performance one could get from answering the queries directly. Finally, they propose algorithms to minimize this accuracy tradeoff and perform some experiments to show empirical performance of these algorithms.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "My review focuses primarily on practical and conceptual considerations, rather than the theoretical contribution.\n\nI think the question of how to responsibly produce differentially private statistics for practitioners is important and timely. I find the uncertainty principle result to be interesting and a potentially useful consideration for data providers. \n\nIf I understand correctly, the uncertainty principle is an artefact of the requirement that synthetic data be non-negatively weighted. Nonnegative weights seems a natural requirement, but some survey data (ACS for example) do allow for negatively weighted records. So producing negatively weighted synthetic data would not (as far as I know) be completely out of line with current norms for survey data. Granted, there is at least some confusion over this and one potential solution people use is setting these weights to 0, which would reduce the setting back to your non-negative weights (see [here](https://forum.ipums.org/t/what-do-negative-replicate-weights-mean/2519)).\n\n**Typos/Clarifications/Style**\n\nLine 45: \"Black **or** African Americans”\n\nLine 823 of the full version should be $X_{100}$ rather than $X_{1}00$\n\nThe paper occasionally refers to \"the result\", \"our results\", etc. I understand this to be either lines 56-59 or Theorem 3, depending on the location, but I think this could be made more explicit.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors point out that the uncertainty principle does not apply to all data sets and give appropriate caveats for their empirical work. I think they’ve done a pretty good job discussing limitations.\n\nMy one hesitation on this front is that I don't think I would go as far as to say that this work “suggests that microdata-generating algorithms should be designed as postprocessing algorithms that convert unbiased noisy measurements into microdata.” That may  be good advice, but the uncertainty principle is stated relative only to the max expected per-query squared error metric. I think the authors provide a reasonable justification for why that metric is practically important but I don't think it's obviously more important than other metrics on which synthetic microdata might perform better. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper can be viewed as a response to the anomalies being found in the Census data release. The main result is that any private algorithm that is consistent on micro data must incur an error overhead on either "local" queries (think block populations) or a "global" query (think total population). Without a micro data constraint, one can answer these queries with constant error. With the micro data requirement, the authors show that the error must be asymptotically larger for one of these.
This is an interesting paper that throws light on an important phenomenon and explains the cost of micro data requirement. The authors are encouraged to carefully look at the reviews and address reviewer comments and incorporate relevant clarifications from the rebuttal. I recommend that the paper be accepted.
Decision: Accept (Poster)