Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
main_review: * Strength:
This paper provides a theoretical analysis of the tradeoff between accuracy on populations and accuracy on sub-populations.

* Weakness:
- the paper is not well-written. There are many undefined terms and notations. 
- the keyword microdata has to be rigorously defined
- the theoretical results are somewhat incremental, given earlier work, e.g., the tradeoff analyses in [3] 
- It is unclear how tight the derived lower bounds are. The practical implication of these bounds needs to be discussed.
limitations_and_societal_impact: yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: The paper is well written and is comprehensible on its contributions.
I 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.
Reference 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.
Baseline 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.

Minor:
Though I only found arxiv version of [3], I could not find "uncertainty principle" explicitly defined.

After author response:
Thank you for addressing my questions and clarifying some misunderstandings. I updated my score accordingly.
limitations_and_societal_impact: yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 
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.

Quality: 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.

Clarity: The paper is well organised and clearly written with minor typos and things that can be better clarified, such as,

- In section 3.1, 'Theorem 3 says that ... produce positively weighed errors', should be 'weighted'.
- 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.
- In theorem 4, 'Given privacy parameters ... There', the 'T' should not be capitalised.

Significance: 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.
limitations_and_societal_impact: The authors have discussed as thoroughly as possible the limitations of their work.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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. 

The 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.

The 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.

Finally, they propose a set of benchmark data sets and evaluate their algorithms and compare to common baselines.
main_review: Originality:
The 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.
Additionally, 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.

Quality:
The 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.)

Clarity:
The 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).

Personally, 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).


Significance:
The 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.
The 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).

Some open questions:
- 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)?
- 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?
- 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?

Minor comments:
- line 119: "then the algorithm that M that releases": superfluous "that" after "then the algorithm"
- 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?

Update:

I thank the authors for their response to the questions I raised during my initial review. My first two questions stand fully addressed.

However, 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.

Upon 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.

This 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.

Now, 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.

I 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.


limitations_and_societal_impact: The authors point out the limitations of their analysis and the proposed algorithms clearly.

There 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_title: null

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)