Privately Counting Partially Ordered Data

Authors: Matthew Joseph, Mónica Ribero, Alexander Yu
Primary area: alignment, fairness, safety, privacy, and societal considerations
Keywords: differential privacy

Abstract:
We consider differentially private counting when each data point consists of $d$ bits satisfying a partial order. Our main technical contribution is a problem-specific $K$-norm mechanism that runs in time $O(d^2)$. Experiments show that, depending on the partial order in question, our solution dominates existing pure differentially private mechanisms and can reduce their error by an order of magnitude or more.

Decision: accept (poster)
Reviewer scores: 8, 6, 8, 5

Reviews and discussion:
<thread>
creation date:
1729774809925

thread_type:
official_review

<thread_object>
creator: reviewer_dkvy

<content>
summary:
The paper primarily focuses on differentially private counting when data points satisfying a partial order. Previous best approaches takes time $\tilde{O}(d^{2+\omega})$ where $\omega\geq 2$ is the matrix multiplication exponent. In contrast, this work provides a fast sampler for the induced norm ball that runs in $O(d^2)$. To achieve this, this work starts with connecting the poset ball to double order polytope, then reduces the problem to uniformly sampling a non-interfering pair of chains with the results from Chappell and finally to sampling an extended bipartition. Experiments are conducted to show that the final sampler reduces error over existing DP mechanisms. To complement the sampler, this work also shows a negative result for rejection sampling.

strengths:
S1: This paper addresses the problem by providing a sampler with more than cubic speedup over the previous algorithms. 

S2: The proof path leading to the final sampler is clear and well-organized.

S2: This paper also investigates the rejection sampling and provides a negative result. 

S3: The paper conducts experiments on both synthetic and real-world partial orders to demonstrate error reductions of their sampler.

weaknesses:
W1: The comparison with previous research, particularly with the work of Joseph & Yu, does not seem sufficiently thorough. (summarized in the questions)

W3: The results of the experiments appear to be incomplete (also summarized in questions.)

questions:
Q1: Although the authors have introduced the differences between their work and that of Joseph & Yu in the related work section, they do not seem to have adequately demonstrated the innovative aspects of their work. Furthermore, the structure of the paper appears similar, as Joseph & Yu also considered rejection sampling. It seems that this paper merely modifies the sampling technique based on changes in the characteristics of the input data, without showcasing its unique core technology.

It would be beneficial if the authors can provide a more detailed comparison, such as explaining how the data considered in this paper differs from that considered by Joseph & Yu; why their sampling technique is not well-suited to our current data; and how the sampling method proposed in this paper leverages the new data characteristics and what innovations it introduces.


Q2: The experiments in the paper only investigate the error reduction of the sampler. Since the main contribution of the paper is a sampler faster then previous algorithms, it would be beneficial for the authors to conduct experiments that demonstrate speedup of their algorithm and compare it with former approaches.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730693139540

thread_type:
official_review

<thread_object>
creator: reviewer_jicc

<content>
summary:
Differentially private algorithms for counting queries have a long history and mechanisms that add carefully chosen noise when queries have some structure can improve accuracy. Some of these algorithms are often used in practice, e.g. by the US Census Bureau. For the case of pure DP, the K-norm mechanism of Hardt and Talwar improves on the Laplace mechanism that does not exploit the structure of the queries. The algorithm however requires sampling from the “sensitivity polytope” defined by the queries.

The current paper studies this sampling problem for the case when the queries have a “partially ordered” structure. E.g. surveys often have a sequence of questions where a No answer to a question implies a no answer to the next question. This imposes a constraint that the answer to $Q_{i+1}$ can be 1 only if $Q_{i}$ has answer 1. The authors study the more general case of partial orders.

The main contribution of this work is to show an efficient algorithm to sample from the sensitivity polytope defined by a partial order. For the case of d queries, the proposed algorithm runs in time $O(d^2)$. The paper follows a general schema in recent work by Joseph and Yu, where the sensitivity polytope is expressed as a union of simplexes. A simplex is easy to sample from, and thus the problem reduces to sampling a random simplex proportional to its volume. While Joseph and Yu used this approach for some set of problems, their work does not cover this natural set of constraints, and this is addressed in the current work.

The main contribution in my mind is to bring in the technical tools from recent works in the geometry of the poset polytopes, and apply them to this natural problem. The authors also do experiments comparing their algorithm to using K-norm for an \ell_p norm, and show that for random posets, using the K-norm improves noticeably the error in the estimate for random posets, as well as for an National Health Interview Survey.

strengths:
- Brings in tools from another research area to improve algorithms/bounds for a natural and practical problem

weaknesses:
- The paper is difficult to read for someone who is not an expert in partial orders.

questions:
- The recursive K-norm mechanism can improve the error bounds. It would be valuable to see the error comparison. Relatedly, Hardt and Talwar seem to have lower bounds and one can also minimize over matrix mechanisms. It would be valuable to compute the lower bounds and see how far off they are from the upper bounds here.
- For larger d, I would expect that (eps, delta)-DP algorithms with a small delta would become competitive quickly, and have the advantage of being easier to sample from. A comparison even with the simplest Gaussian mechanism, for a small delta (say 10^-6 - 10^-9) would make the paper better.
- In the case of surveys, the poset structure would be further restricted to a “product structure”, where Q2-Q5 may depend on Q1, and Q7-Q9 may depend on Q6, but Q1-Q5 and Q6-Q10 are independent of each other. In this case, you should be able to reduce the run time from d^2 to dk, where k is the size of the largest dependency. This seems like a natural extension of the current work and should be written down.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730774572614

thread_type:
official_review

<thread_object>
creator: reviewer_a51u

<content>
summary:
The paper presents a sampling algorithm that samples from a K-norm mechanism on an induced ball for counting partially ordered data. The algorithm presented in the paper runs in $O(d^2)$ time instead of $O(d^{2+\omega})$ time.

strengths:
The paper proposes a sampling mechanism for a special instantiation of K-norm mechanism that improves the state of the art sampling algorithm by a factor of $O(d^\omega)$.

weaknesses:
I found the paper rather hard to read and also difficult to figure out what are the contributions of the authors and what follows more or less from Chappell et al. (2017). I suggest that the authors make it explicitly clear by giving a high level overview of their proof stating clearly what steps requires their proof and what was already known in the literature. To me, it feels like the main contribution is the proof of Lemma 3.14, but I can be wrong and would love to stand corrected. 

If the authors can give me a better understanding of which aspect of their paper is new, I would be more than happy to increase the score.

questions:
Please give us a good overview of which is your contribution and what are the challenges faced when using the previous algorithms to perform the sampling.

Also, what is the best known sampling algorithm that runs in time $O(d^{2+\omega})$? What happens if that sampling algorithm is instantiated with the set up that the authors propose? What difference from that sampling algorithm do the authors take?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731116416914

thread_type:
official_review

<thread_object>
creator: reviewer_dnfd

<content>
summary:
This work studies differentially private summation of items that satisfy a partial order. The authors show that the problem can be solved in time $d^2$ where $d$ is the number of bits and outperforms existing private algorithms.

strengths:
1. Summing over items with partial orders is a fundamental problem that has not been fully studied under differential privacy. 
2. The proposed algorithm is very time-efficient, only quadratic in the number of bits. The speed-up is significant over some simple sampling algorithms
3. The estimation error is much better than standard privacy algorithms based on $\ell_{\infty}$ norm.

weaknesses:
1. The algorithm is only for pure differential privacy. Approximate DP is sometimes more practical in many applications.
2. It would be helpful to the readers to provide a high-level overview of the algorithm and why it improves over standard algorithms through a simple example.

questions:
How can the algorithm be adapted to approximate DP and achieve better results than pure DP?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731963088116

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Overall response

comment:
Thanks for the reviews! We have uploaded a new submission with additions highlighted in red. We make one overall note and then provide individual reviewer responses below.

While preparing the response, we noticed an off-by-one error in our experiments. For some experiments (the random posets and NHIS data), the poset does not have a root, so we add one, run the K-norm mechanism on the $(d+1)$-dim data, and then output the last $d$ dimensions of the final output (i.e., drop the added root dimension) as discussed at the beginning of Section 4 in both the original and revised paper. However, our initial submission experiments did so using a radius drawn from a $\Gamma(d+1, 1/\varepsilon)$ distribution, while the correct distribution is $\Gamma(d+2, 1/\varepsilon)$. The new submission corrects this, and the result is a slightly reduced improvement. Note that the change is small – the most dramatic change occurs for the NHIS data, where the average improvement drops from 60% to 50%. Nonetheless, we highlight this change for transparency.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper studies the problem of designing differentially private algorithms for counting queries that have a partially ordered structure. The main contribution of the paper is an algorithm guaranteeing pure differential privacy while achieving a running time that is significantly faster than prior work.

Designing differentially private algorithms for counting queries is an important direction with many applications. The direction of exploiting additional structure is a well motivated one. The algorithm proposed is very efficient and practical, and the experimental evaluation shows that the proposed algorithm achieves significant improvements in the error. Most of the reviewers appreciated the main contribution and showed strong support for the paper. One of the reviewers was concerned that the paper is not sufficiently novel compared to the prior work of Joseph and Yu. The author response addressed this concern and noted that the techniques are quite different.