Privately Counting Partially Ordered Data

We have expanded the discussion of the Joseph and Yu paper in the Related Work section (see updated submission). To summarize, in both papers, the primary technical contribution is developing a fast sampler for the norm ball induced by the sensitivity space. Since the papers consider different problems, these lead to different norm balls. The original idea for sampling such balls to run the K-norm mechanism was introduced by HT10 (https://arxiv.org/abs/0907.3754), but it is impractically slow without these fast and problem-specific samplers. Therefore, while both our paper and Joseph and Yu develop fast problem-specific samplers, the techniques required are quite different, because the norm balls are completely different geometric objects and each sampler has a structure that is highly specific to the object being sampled. For example, their sum polytope triangulation is indexed by permutations with a fixed number of ascents, while ours is indexed by pairs of non-interfering chains in the Birkhoff lattice, and developing uniform samplers for these different objects requires different approaches.

It is hard to provide an empirical comparison to the general $\tilde O(d^{3+\omega})$ sampler given by Laddha et al. (https://arxiv.org/abs/1911.05656), as their algorithm is quite complicated and relies on asymptotic statements that make accurate implementation difficult – to the best of our knowledge, no public implementation of the algorithm exists. However, we have added empirical runtimes for our algorithm (Section 4.5) demonstrating that our sampler runs in under half a second on a typical personal computer for problems at the scale considered in our experiments. We hope that the combination of fast empirical and theoretical runtimes for our algorithm and slow theoretical runtime for the general sampler are sufficient evidence of the speed improvement.

Please see the updated submission for a) language clarifying our contributions and the relationship between our work and Chappell et al. (see response to Reviewer a51u for details), and b) a concrete example based on the path poset (see response to Reviewer dNFD for details). We hope this will make the algorithm easier to understand.

The chief weakness of the recursive K-norm mechanism given by HT10 is that it runs the K-norm mechanism on successively smaller subspaces by approximating their covariance matrices. Our efficient sampler still takes $O(d^2)$ time to sample the poset ball once, and their algorithm requires approximately $O(d^4)$ samples to approximate the relevant covariance matrices in each subspace. This blows up the runtime enough to be impractical. If desired, we can add a short discussion of this issue to the Related Work section -- we omitted it in our paper, as Joseph and Yu (https://arxiv.org/pdf/2309.15790, Section 1.2) makes the same point. Regarding lower bounds, we are not sure how to compare the asymptotic lower bounds given by HT10 to the empirical upper bounds provided here – do you have something specific in mind?

For $(1, 10^{-6})$-DP, the Gaussian mechanism is dominated by the $\ell_\infty$ mechanism for the $d \leq 50$ used in our experiments. We have added a short note discussing this in the revised submission (see the end of Section 4.1 and Appendix B.2).

The example provided is a forest with two disconnected components. However, the poset ball of a forest does not in general decompose as a direct sum of the poset balls of its connected components. To see this, let $S(G) = V(O(G)) \cup -V(O(G))$ be the vertices of the poset ball of graph $G$, and let $CH(Z)$ denote the convex hull of points in a set $Z$. Then $CH(S(X \cup Y)) \neq CH(S(X)) \oplus CH(S(Y))$, where $\oplus$ is the direct sum operation. To see this, let $X$ and $Y$ be two different single vertex graphs. Then $CH(S(X)) \oplus CH(S(Y))$ is $[-1,1] \oplus [-1,1]$ which is the $\ell_{\infty}$ unit ball. On the other hand, $CH(S(X \cup Y))$ is the convex hull of the unit square in the positive quadrant and its negation. Consequently, sampling independently from each component and combining the samples via direct sum would not yield a uniform sample from the poset ball.

We have attempted to add a high-level overview of the relationship between our work and Chappell et al. at the beginning of Section 3. We have also added more subsection headings to further clarify our proof structure. Briefly, our theoretical contributions are a) observing the connection between the privacy problem of counting partially ordered data and the combinatorics work of Chappell et al. and translating between the two settings (specifically, we show that sampling from the k-norm mechanism is equivalent to sampling from a double order polytope (Lemma 3.4)), b) proving a bijection between the non-interfering chains of Chappell et al. and extended bipartitions (Lemma 3.13), and c) constructing a fast uniform sampler for the relevant extended bipartitions (Lemma 3.14). Note in particular that extended bipartitions are objects original to our paper, and while Chappell et al. derive a triangulation of the double order polytope, they do not discuss sampling any of those objects.

The best alternative sampler is due to Laddha et al. (https://arxiv.org/abs/1911.05656), and a short discussion appears at the end of Section 2.2. Note that this sampler takes time $\tilde O(d^{3+\omega})$ where $\omega > 2$. The primary operational difference between their sampler and ours is that their sampler can be applied to any polytope; in contrast, our sampler is tailored only to the poset ball, and relies on knowledge of its structure to sample quickly. Note also that applying their sampler only achieves $O(\varepsilon)$-DP, as it is an approximate sampler, whereas ours is exact.

We agree that extending this approach to approximate DP is a natural next problem. We attempted to discuss this problem in the Discussion section at the end of the paper. Recapping the brief discussion there, to extend to approximate DP, it suffices to find the minimum ellipse (in terms of expected squared $\ell_2$ norm) that contains the poset ball, as done by Joseph and Yu (https://arxiv.org/abs/2309.15790). Finding the minimum enclosing ellipse for general high-dimensional polytopes is a difficult optimization problem, and the general approach relies on semidefinite programs. This approach can be very slow (for details, see the discussion at the end of Section 2.2 in Joseph and Yu). Joseph and Yu circumvent this difficulty by exploiting the symmetry of sum, count, and vote polytopes around the vector $(1,...,1)$, a property not all poset balls possess. Consider, for example, the simple poset with elements $v_1$ and $v_2$, where $v_1 > v_2$: the vector $(1,0)$ is in its ball $P$, while $(0,1)$ is not. This breaks their approach to finding the minimum enclosing ellipse, and it is not clear how to fix this issue.

Several reviewers asked for a simpler high-level overview of the algorithm. We have added an informal discussion of the proof at the beginning of Section 3, as well as an example and experiments based on the path poset ($x_d \leq x_{d-1} \leq \cdots \leq x_1$), as the resulting poset ball is both geometrically simple (it is a linear transformation of the $\ell_1$ ball) and yields a large utility improvement over the $\ell_\infty$ mechanism (see Figure 1 and Section 4.2 in the revised submission).