Privately Counting Partially Ordered Data

## Abstract

Abstract We consider differentially private counting when each data point consists of d 𝑑 d italic_d bits satisfying a partial order. Our main technical contribution is a problem-specific K 𝐾 K italic_K -norm mechanism that runs in time O ⁢ ( d 2 ) 𝑂 superscript 𝑑 2 O(d^{2}) italic_O ( italic_d start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT ) . 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.

## 1 Introduction

A differentially private (DP) [] statistic incorporates randomness to obscure the contribution of any single data point. To achieve this, differentially private algorithms typically require — and, if necessary, enforce — restrictions on the data points. A common restriction is $\ell_{p}$ sensitivity: if the statistic $T$ is a vector in $\mathbb{R}^{d}$, adding a user’s data point must not change the $\ell_{p}$ norm of $T$ by more than $\Delta_{p}$. This framework is generic enough to apply to a wide variety of problems, but it can yield relatively poor performance for statistics whose sensitivity is not tightly characterized by an $\ell_{p}$ norm. One such statistic is counting on *partially ordered data*.

As a straightforward running example, the National Health Interview Survey [] has been administered annually since 1957 by the Center for Disease Control. The Hypertension section of the 2024 survey first asks if the respondent has been told they have hypertension and then asks if they have been told multiple times. The survey structure requires a respondent to answer “yes” to the first question in order to answer “yes” to the second; equivalently, if the answers are given as binary vector $x$, the survey structure imposes partial order $x_{2}\leq x_{1}$. A count of this partially ordered data then records the number of “yes” responses to each question. Other examples of partially ordered data include software library dependencies, coursework prerequisites, and any data encoded using directed acyclic graphs.

It is possible to apply $\ell_{p}$ sensitivity to partially ordered data. In the survey example, a respondent can answer “yes” to every question, so the vector of counts has $\ell_{1}$ sensitivity $d$. However, this analysis also protects against inputs that cannot occur, as the binary and order constraints means that no response can have the form $(d,0,\ldots,0)$ or $(0,1,\ldots)$. In this sense, straightforward application of Laplace (or other $\ell_{p}$ mechanism) noise may be “loose”.

### 1.1 Contributions

Our main technical contribution is an efficient implementation of the $K$-norm mechanism [] for counting partially ordered data. Our solution can be applied to any partial order, satisfies pure differential privacy, and runs in time $O(d^{2})$ (Theorem 3.15). This provides a more than cubic speedup over the fastest general polytope sampler and is provably exponentially faster than any $\ell_{p}$ ball rejection sampler (Theorem 3.17). Experiments using both synthetic and real-world partial orders demonstrate significant error reductions over existing DP mechanisms (Section 4).

### 1.2 Related Work

Joseph and Yu [] previously constructed efficient implementations of the $K$-norm mechanism to obtain better noise distributions for the problems of (contribution-bounded) sum, count, and vote. For a longer discussion of the $K$-norm mechanism, its variants, and its relation to other query-answering solutions like the projection [, ], matrix [, ], and factorization [, ] mechanisms, we refer the interested reader to their paper; here, we note that these mechanisms can be viewed as general but possibly slow approximations of optimal constructions of problem-specific private additive noise. In contrast, we provide a problem-specific but optimal and fast construction.

The simplest difference between our work and that of Joseph and Yu [] is that we consider different problems that require different sampling techniques. In more detail, these different problems are characterized by different combinatorial objects. In Joseph and Yu [], their sum and vote polytopes are based on a truncated hypercube and permutohedron, respectively. Here, the poset polytope is most closely related to the double poset polytope. Similarly, though our samplers are also based on identifying an efficiently sampleable triangulation of the polytope, the triangulations themselves are different: the 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.

## 2 Preliminaries

### 2.1 Differential Privacy

The material in this subsection is largely adapted from the preliminaries of Joseph and Yu [], who derived efficient instances of the $K$-norm mechanism for different problems. We use pure differential privacy, in the add-remove model.

###### Definition 2.1 ( Dwork et al. [ 3 ] ) .

Databases $X,X^{\prime}$ from data domain $\mathcal{X}$ are *neighbors* $X\sim X^{\prime}$ if they differ in the presence or absence of a single record. A randomized mechanism $\mathcal{M}:\mathcal{X}\to\mathcal{O}$ is *$\varepsilon$-differentially private* (DP) if for all $X\sim X^{\prime}\in\mathcal{X}$ and any $S\subseteq\mathcal{O}$,

$$ $\mathbb{P}_{\mathcal{M}}\left[\mathcal{M}(X)\in S\right]\leq e^{\varepsilon} \mathbb{P}_{\mathcal{M}}\left[\mathcal{M}(X^{\prime})\in S\right].$ $$

Our solution will apply the $K$-norm mechanism.

###### Lemma 2.2 ( Hardt and Talwar [ 6 ] ) .

Given statistic $T$ with $\|\cdot\|$-sensitivity $\Delta$ and database $X$, the *$K$-norm mechanism* has output density $f_{X}(y)\propto\exp\left(-\frac{\varepsilon}{\Delta}\cdot\|y-T(X)\|\right)$ and satisfies $\varepsilon$-DP.

We apply an instance of the $K$-norm mechanism chosen using our statistic’s *sensitivity space*.

###### Definition 2.3 ( Kattis and Nikolov [ 8 ], Awan and Slavković [ 1 ] ) .

The *sensitivity space* of
statistic $T$ is $S(T)=\{T(X)-T(X^{\prime})\mid X,X^{\prime}\text{ are neighboring databases}\}$.

Sensitivity spaces that induce norms are particularly interesting, as the corresponding $K$-norm mechanisms enjoy certain notions of optimality.

###### Lemma 2.4 .

If set $W$ is convex, bounded, absorbing (for every $u\in\mathbb{R}^{d}$, there exists $c>0$ such that $u\in cW$), and symmetric around 0 ($u\in W\Leftrightarrow-u\in W$), then the function $\|\cdot\|_{W}\colon\mathbb{R}^{d}\to\mathbb{R}_{\geq 0}$ given by $\|u\|_{W}=\inf\{c\in\mathbb{R}_{\geq 0}\mid u\in cW\}$ is a norm, and we say $W$ induces $\|\cdot\|_{W}$.

###### Definition 2.5 .

If statistic $T$ has a sensitivity space convex hull $CH(S(T))$ satisfying Lemma 2.4, we say $T$ *induces a norm*, and call $CH(S(T))$ the *induced norm ball* of $T$.

Awan and Slavković [] show that the instance of the $K$-norm mechanism using a statistic’s induced norm is optimal with respect to entropy and conditional variance (see Sections 3.2 and 3.3 of their paper for details). The only remaining challenge is running the resulting mechanism.

###### Lemma 2.6 ( Hardt and Talwar [ 6 ] ) .

Running the $K$-norm mechanism reduces to sampling the unit ball for the norm $\|\cdot\|$.

Our main technical contribution is therefore a fast sampler for the induced norm ball for counting partially ordered data. This is a $d$-dimensional polytope with $\Omega(d)$ constraints. Applying the best general sampler takes time $\tilde{O}(d^{2+\omega})$ where $\omega\geq 2$ is the matrix multiplication exponent (Theorem 1.5 of Laddha et al. []), and achieving a close enough approximation for $O(\varepsilon)$-DP adds another $O(d)$ factor (Appendix A of Hardt and Talwar []).

###### Definition 2.1 ( Dwork et al. [ 3 ] ) .

###### Lemma 2.2 ( Hardt and Talwar [ 6 ] ) .

###### Definition 2.3 ( Kattis and Nikolov [ 8 ], Awan and Slavković [ 1 ] ) .

###### Lemma 2.4 .

###### Definition 2.5 .

###### Lemma 2.6 ( Hardt and Talwar [ 6 ] ) .

### 2.2 Partially Ordered Data

Throughout, we assume that our goal is to compute a sum $T(X)=\sum_{x\in X}x$ of length-$d$ binary vectors with bits that satisfy a partial order.

###### Definition 2.7 .

A *partially ordered set* or *poset* $(P,\preceq)$ is a finite set $P$ together with a reflexive, transitive, and anti-symmetric relation $\preceq$. If $p_{1},p_{2}\in P$ and $p_{1}\preceq p_{2}$, we say that $p_{1}$ is a *child* of $p_{2}$ and $p_{2}$ is a *parent* of $p_{1}$. A *linear extension* of poset $(P,\preceq)$ is a total ordering $(P,\preceq^{*})$ that preserves $\preceq$, i.e. an ordering of the elements of $P$ given by $p_{1}\preceq^{*}p_{2}\preceq^{*}\ldots\preceq^{*}p_{d}$ such that $p_{i}\preceq p_{j}$ implies $i<j$. We assume that a poset is given in the form of a $|P|\times|P|$ binary matrix $M$ where $M_{ij}=1\Leftrightarrow p_{i}\preceq p_{j}$. We say a length-$|P|$ binary vector $x$ is *partially ordered* if $p_{i}\preceq p_{j}$ implies $x_{i}\leq x_{j}$.

We also assume that each poset has a single root.

###### Assumption 2.8 .

The poset $(P,\preceq)$ has a root $r\in P$ such that $p\preceq r$ for all $p\in P$.

For surveys, this corresponds to a question asking if the respondent wants to take the survey at all, and allows us to count nonrespondents. Our mechanism is optimal for these posets in the sense described by Awan and Slavković []. Note also that if we are instead given a poset without a root, we can simply add a root, apply our mechanism, and ignore the added dimension in the final output, as done in our experiments. By post-processing, this does not alter the privacy guarantee.

###### Definition 2.7 .

###### Assumption 2.8 .

## 3 An Efficient Mechanism

### 3.1 Poset Ball

As described in Section 2.1, an efficient application of the optimal $K$-norm mechanism for counting partially ordered data reduces to sampling the norm ball induced by its sensitivity space. We start with some basic results about the structure of this norm ball. Throughout, we denote our original poset by $P^{*}$. Recall from 2.8 that we assume the poset $(P^{*},\preceq)$ ordering our data points has a root $r$ such that $p\preceq r$ for all $p\in P^{*}$; we omit this assumption for the rest of this section.

###### Lemma 3.1 .

Let $T_{(P^{*},\preceq)}(X)=\sum_{x\in X}x$ be a statistic summing data points $x$ that satisfy a partial order $(P^{*},\preceq)$ (Definition 2.7). Then $T_{(P^{*},\preceq)}$ induces a norm.

###### Proof.

We verify the conditions in Lemma 2.4. We write $T=T_{(P^{*},\preceq)}$ for brevity.

$CH(S(T))$ is a convex hull and so immediately convex. Let $V(CH(S(T)))$ be the set of vertices of $CH(S(T))$. By the definition of sensitivity space, the vertices of $CH(S(T))$ are the length-$|P^{*}|$ partially ordered binary vectors and their negations. There are finitely many vertices, so $CH(S(T))$ is bounded. Any point $p\in CH(S(T))$ is a convex combination of the vertices $\sum c_{i}v_{i}$, and $v_{i}\in V(CH(S(T)))$ implies $-v_{i}\in V(CH(S(T)))$, so $-p=\sum c_{i}(-v_{i})\in CH(S(T))$. Thus, $CH(S(T))$ is symmetric around the origin.

It remains to show $CH(S(T))$ is absorbing. Consider any linear extension $(P^{*},\preceq^{\prime})$ of $(P^{*},\preceq)$. Then $(P^{*},\preceq^{\prime})$ has all of the relations in $(P^{*},\preceq)$, so $S(T_{(P^{*},\preceq^{\prime})})\subset S(T_{(P^{*},\preceq)})$, and $CH(S(T_{(P^{*},\preceq^{\prime})}))\subset CH(S(T_{(P^{*},\preceq)}))$. Define $\{v_{1},\ldots,v_{d}\}$ to be the set of binary vectors where $v_{i}$ is the vector whose first $i$ entries are 1 while the rest are 0. Then $V(CH(S(T_{(P^{*},\preceq^{\prime})})))$ is $\{\pm v_{1},...,\pm v_{d}\}$. Since $\{v_{1},...,v_{d}\}$ forms a basis of $\mathbb{R}^{d}$, there is an invertible linear map $A$ mapping $\{v_{1},...,v_{d}\}$ to the standard basis. In particular, $A(CH(S(T_{(P^{*},\preceq^{\prime})})))$ is the unit $\ell_{1}$ ball $B_{1}^{d}$. Let $b$ be a small origin centered ball around 0 in $B_{1}^{d}$. Then $A^{-1}(b)$ is a small origin centered ellipsoid in $CH(S(T_{(P^{*},\preceq^{\prime})}))$, i.e. 0 is an interior point of $CH(S(T_{(P^{*},\preceq^{\prime})}))$. Since $S(T_{(P^{*},\preceq^{\prime})})\subset S(T_{(P^{*},\preceq)})$, it follows that $CH(S(T_{(P^{*},\preceq)}))$ is absorbing.
∎

We shorthand $T$’s induced norm ball as the *poset ball*. The next result shows that the poset ball can be reinterpreted as an object from combinatorics, the double order polytope. This interpretation allows us to apply results about the double order polytope from Chappell et al. []. Reasoning about the double order polytope requires some additional definitions related to posets.

###### Definition 3.2 .

A *double poset* is a triple $(P,\preceq_{+},\preceq_{-})$ where $P_{+}=(P,\preceq_{+})$ and $P_{-}=(P,\preceq_{-})$ are posets on the same ground set. A double poset is *compatible* if $P_{+}$ and $P_{-}$ have a shared linear extension.

###### Definition 3.3 ( [ 2 ] ) .

Let $\mathcal{P}_{1},\mathcal{P}_{2}\subset\mathbb{R}^{d}$ be polytopes. The *Cayley sum* of $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$ is defined by ${\mathcal{P}_{1}\boxplus\mathcal{P}_{2}=CH(\{1\}\oplus\mathcal{P}_{1}\cup\{-1
\}\oplus\mathcal{P}_{2})}$. Define $\mathcal{P}_{1}\boxminus\mathcal{P}_{2}=\mathcal{P}_{1}\boxplus-\mathcal{P}_{2}$. The *order polytope* $\mathcal{O}(P)$ of a poset $(P,\preceq)$ is the set of all order preserving functions $f:P\rightarrow[0,1]$ such that $0\leq f(a)\leq f(b)\leq 1$ for all $a,b\in P$ where $a\preceq b$. The *double order polytope* $\mathcal{O}_{2}(P)$ of a double poset $(P,\preceq_{+},\preceq_{-})$ is $\mathcal{O}(P_{+})\boxminus\mathcal{O}(P_{-})$.(^1^11This is a slight modification of the definition of the double order polytope given by Chappell et al. [], but the change does not meaningfully affect the properties of this structure (see Remark A.1 for details).)

We can now state the connection between the poset ball and double order polytope.

###### Lemma 3.4 .

The poset ball for poset $(P^{*},\preceq)$ is $\mathcal{O}_{2}(P^{*}-r)$, the double order polytope on the double order poset $(P^{*}-r,\preceq,\preceq)$.

###### Proof.

Let $S$ be the set of functions $f:P^{*}\rightarrow\{0,1\}$ such that $0\leq f(a)\leq f(b)\leq 1$ for all $a,b\in P^{*}$ where $a\preceq b$. We can view functions in $S$ as $|P^{*}|$-dim binary vectors in the natural way. Recall that the poset ball is $CH(S\cup-S)$. Equivalently, it is $CH(\mathcal{O}(P^{*})\cup-\mathcal{O}(P^{*}))$. We apply the following general result about the convex hulls of reflected polytopes. A similar result is stated without proof in Chappell et al. []; for completeness, a proof appears in Appendix A.

###### Claim 3.5 .

Let $\mathcal{P}$ be a $(d-1)$-dim convex polytope in $\mathbb{R}^{d}$ lying in the hyperplane $x_{1}=1$. Let $\mathcal{P}^{\prime}=\mathcal{P}\cup\{0\}$. Then $V(CH(\mathcal{P}^{\prime}\cup-\mathcal{P}^{\prime}))=V(\mathcal{P})\cup V(-
\mathcal{P})$.

By 3.5, the vertices of $CH(\mathcal{O}(P^{*})\cup-\mathcal{O}(P^{*}))$ are $V(\mathcal{O}(P^{*}))\cup V(-\mathcal{O}(P^{*}))-\{0\}$. The vertices in $V(\mathcal{O}(P^{*}))-\{0\}$ are of the form ${1}\oplus v$ where $v$ is a vertex of $V(\mathcal{O}(P^{*}-r))$, and the first dimension corresponds to the $r$-dimension. In other words, the vertices of this shape are exactly the vertices of $\mathcal{O}_{2}(P^{*}-r)$ , the double order polytope on the double poset $(P^{*}-r,\preceq,\preceq)$.
∎

By Lemma 3.4, our new goal is to construct a fast sampler for the double order polytope $\mathcal{O}_{2}(P^{*}-r)$.

###### Lemma 3.1 .

###### Proof.

###### Definition 3.2 .

###### Definition 3.3 ( [ 2 ] ) .

###### Lemma 3.4 .

###### Proof.

###### Claim 3.5 .

### 3.2 Double Order Polytopes and Double Chain Polytopes

We sample $\mathcal{O}_{2}(P^{*}-r)$ by constructing a triangulation that decomposes it into disjoint $d$-dimensional simplices of equal volume. By this construction, it suffices to sample one of the simplices uniformly at random and then return a uniform random sample from the chosen simplex. The following result about uniformly sampling a simplex is folklore; we take the statement from Joseph and Yu [].

###### Lemma 3.6 .

A collection of points $x_{0},\ldots,x_{d}\in\mathbb{R}^{n}$ with $n\geq d$ are *affinely independent* if $\sum_{i=0}^{d}\alpha_{i}x_{i}=0$ and $\sum_{i=0}^{d}\alpha_{i}=0$ implies $\alpha=0$. A *$d$-simplex* is the convex hull of $d+1$ affinely independent points and can be uniformly sampled in time $O(d\log(d))$.

Since sampling a simplex is easy, it remains to find a triangulation of $\mathcal{O}_{2}(P^{*}-r)$ into simplices. For completeness, the following definition formalizes the notion of a triangulation.

###### Definition 3.7 .

Let $\mathcal{P}\subset\mathbb{R}^{d}$ be a polytope. For $0\leq k\leq d-1$, a *proper $k$-dim face* of $\mathcal{P}$ is an intersection $I$ of the form $H\cap\partial\mathcal{P}$ of a $(d-1)$-dim hyperplane $H$ with the boundary of $\mathcal{P}$, such that the $I\subset\partial\mathcal{P}$ and $\dim(I)=k$. A *subdivision* of $\mathcal{P}$ is a collection of $d$-dim polytopes $P_{1},...,P_{m}$ such that $\mathcal{P}=\cup_{i=1}^{m}P_{i}$ and for each $1\leq i<j\leq m$ the (possibly empty) set $P_{i}\cap P_{j}$ is a proper face of each of $P_{i}$ and $P_{j}$. A *triangulation* of $\mathcal{P}$ is a subdivision containing only simplices. A simplex with vertices in a lattice $\Lambda$ is *unimodular* if it has minimal volume. A triangulation is unimodular if all of its simplices are unimodular.

We use a result from Chappell et al. [] that provides a mapping between the double order polytope and a related geometric object, the double chain polytope.

###### Definition 3.8 ( [ 2 ] ) .

Given poset $P$, a *chain* is a sequence of (strictly) increasing elements in $P$. The *chain polytope* $\mathcal{C}(P)$ is the set of functions $g:P\rightarrow\mathbb{R}^{\geq 0}$ such that $g(a_{1})+...+g(a_{k})\leq 1$ for all chains $a_{1}\preceq...\preceq a_{k}$ of $P$. The *double chain polytope* $\mathcal{C}_{2}(P)$ of a double poset $(P,\preceq_{+},\preceq_{-})$ is $\mathcal{C}(P_{+})\boxminus\mathcal{C}(P_{-})$

###### Lemma 3.9 (Theorem 4.3 [ 2 ] ) .

For any compatible double poset $(P,\preceq_{+},\preceq_{-})$, there is an explicit homeomorphism between the double chain polytope $\mathcal{C}_{2}(P)$ and the double order polytope $\mathcal{O}_{2}(P)$.

Conveniently, the mapping transfers a triangulation of the double chain polytope to a triangulation of the double order polytope also due to Chappell et al. []. This triangulation will be indexed by objects called non-interfering pairs of chains.

###### Definition 3.10 ( [ 2 ] ) .

Given poset $(P,\preceq)$, $I\subset P$ is a *filter* if $x\in I$ and $x\preceq y$ implies $y\in I$, and the *Birkhoff poset* $\mathcal{J}(P)$ is the poset given by the filters of $P$ ordered by inclusion. Given double poset $(P,\preceq_{+},\preceq_{-})$, for chains of filters $C_{+}\subset\mathcal{J}(P_{+})$ and $C_{-}\subset\mathcal{J}(P_{-})$, we say the pair of chains $C=(C_{+},C_{-})$ is *non-interfering* if $\min(J_{+})\cap\min(J_{-})=\emptyset$ for all $J_{+}\in C_{+},J_{-}\in C_{-}$, where $\min(\cdot)$ denotes the set of minimal elements of the filter. Moreover, we denote by $\Delta^{ni}(P)$ the collection of non-interfering pairs of chains.

We therefore obtain the following triangulation of the double order polytope indexed by non-interfering pairs of chains. This follows from Corollary 4.1, Theorem 4.3, and Equation 13 of Chappell et al. [].

###### Lemma 3.11 ( Chappell et al. [ 2 ] ) .

Let $(P,\preceq_{+},\preceq_{-})$ be a double poset. For $L\subset\mathcal{J}(P)$, define $F(L)=CH(\{\mathbbm{1}_{J}\mid J\in L\})\subset\mathbb{R}^{|P|}$. For non-interfering pair of chains $C=(C_{+},C_{-})$ of size $|C|=|C_{+}|+|C_{-}|=|P|+1$, define map $\bar{F}(C)=F(C_{+})\boxminus F(C_{-})$. Then $\{\bar{F}(C)\mid C\in\Delta^{ni}(P)\}$ is a triangulation of $\mathcal{O}_{2}(P)$ into $|P|$-dimensional simplices. Moreover, given $C$, $\bar{F}(C)$ can be computed in time $O(d^{2})$.

As a result of this triangulation, it now suffices to uniformly sample a non-interfering pair of chains associated with $P^{*}-r$ of size $d+1$. This will be easier, because we can construct a bijection between these pairs and extended bipartitions of $P^{*}-r$ , and extended bipartitions are conceptually simpler than non-interfering pairs of chains.

###### Definition 3.12 .

Given poset $(P,\preceq)$, an *extended bipartition* is a quadruple ${((A,\preceq),(B,\preceq),\preceq_{A},\preceq_{B})}$ where $(A,\preceq),(B,\preceq)$ are subposets of $P$ such that $A\cap B=\emptyset,A\cup B=P$, and $\preceq_{A},\preceq_{B}$ are linear extensions of $(A,\preceq),(B,\preceq)$ respectively.

At a high level, given a non-interfering pair of chains, it can be shown that the set difference between the minimal elements of adjacent filters in each chain has size exactly 1, and that these successive differences form a linear extension of the subposet induced by those elements. Moreover, the ground sets of the two linear extensions form a bipartition of the original ground set. Conversely, given an extended bipartition, we can define a non-interfering pair of chains of filters by treating each suffix of each linear extension of the bipartition as the minimal elements of a filter.

###### Lemma 3.13 .

There is a bijection between the set of non-interfering pairs of chains $C=(C_{+},C_{-})$ of the double poset $(P^{*}-r,\preceq,\preceq)$ of size $|C|=|C_{+}|+|C_{-}|=d+1$ and the set of extended bipartitions of $P^{*}-r$. Moreover, given an extended bipartition, its corresponding non-interfering pair of chains can be computed in time $O(d^{2})$.

###### Proof.

Suppose we have a non-interfering pair of chains $C=(C_{+},C_{-})$ where $|C|=d+1$. Write each chain of filters as $C_{\sigma}=J_{1}^{\sigma}\subsetneq...\subsetneq J_{|C_{\sigma}|}^{\sigma}$ for $\sigma\in\{+,-\}$. Then $|\min(J_{i+1}^{\sigma})-\min(J_{i}^{\sigma})|\geq 1$ for $1\leq i\leq|C_{\sigma}|-1$. Any element $p\in(\min(J_{i+1}^{\sigma})-\min(J_{i}^{\sigma}))$ lies in $J_{i+1}^{\sigma}$. If it also lies in $J_{i}^{\sigma}$, then $p\not\in\min(J_{i}^{\sigma})$ means there exists $p^{\prime}\in J_{i}^{\sigma}$ with $p^{\prime}\preceq p$, but $J_{i}^{\sigma}\subsetneq J_{i+1}^{\sigma}$ then implies that $p\not\in\min(J_{i+1}^{\sigma})$, a contradiction. Thus $(\min(J_{i+1}^{\sigma})-\min(J_{i}^{\sigma}))\subseteq(J_{i+1}^{\sigma}-J_{i}^
{\sigma})$, and similarly for any $j>i$, we have

$$ $(\min(J_{j+1}^{\sigma})-\min(J_{j}^{\sigma}))\subseteq(J_{j+1}^{\sigma}-J_{j}^ {\sigma}).$ $$

Then $J_{i+1}^{\sigma}\subseteq J_{j}^{\sigma}$ implies $(\min(J_{i+1}^{\sigma}-\min(J_{i}^{\sigma}))\cap(\min(J_{j+1}^{\sigma}-\min(J_
{j}^{\sigma}))=\emptyset$.

Let $N_{\sigma}=\cup_{i=1}^{|C_{\sigma}|-1}(\min(J_{i+1}^{\sigma})-\min(J_{i}^{
\sigma}))$. The above implies $|N_{\sigma}|\geq|C_{\sigma}|-1$. Moreover, $N_{+}\cap N_{-}=\emptyset$ since $N_{\sigma}\subset\left(\cup_{i=1}^{|C_{\sigma}|-1}\min(J_{i+1}^{\sigma})\right)$, and $\left(\cup_{i=1}^{|C_{+}|-1}\min(J_{i+1}^{+})\right)\cap\left(\cup_{i=1}^{|C_{
-}|-1}\min(J_{i+1}^{-})\right)=\emptyset$ since $C$ is non-interfering. Thus

$$ $|N_{+}\cup N_{-}|=|N_{+}|+|N_{-}|\geq|C_{+}|+|C_{-}|-2=|C|-2=d-1=|P^{*}-r|.$ $$

But $N_{+}\cup N_{-}\subseteq P^{*}-r$, so $|N_{+}\cup N_{-}|=|P^{*}-r|$. This means that $(N_{+},N_{-})$ partition $P^{*}-r$ and $|\min(J_{i+1}^{\sigma})-\min(J_{i}^{\sigma})|=1$ for $1\leq i\leq|C_{\sigma}|-1$. It follows that $\min(J_{1}^{\sigma})=J_{1}^{\sigma}=\emptyset$. This leads us to the following extended bipartition. Let $a_{i}=\min(J_{|C_{+}|-i+1}^{+})-\min(J_{|C_{+}|-i}^{+})$ for $1\leq i\leq|C_{+}|-1$ and $b_{i}=\min(J_{|C_{-}|-i+1}^{-})-\min(J_{|C_{-}|-i}^{-})$ for $1\leq i\leq|C_{-}|-1$. Since filters are upwards closed, either $a_{i}\preceq a_{j}$ for some $a_{j}\in\{a_{i+1},...,a_{|C_{+}|-1}\}$ or $a_{i}$ is incomparable to each element of $\{a_{i+1},...,a_{|C_{+}|-1}\}$. In either case, $a_{1}\preceq_{A}...\preceq_{A}a_{|C_{+}|-1}$ is a linear extension of $N_{+}$, and similarly $b_{1}\preceq_{B}...\preceq_{B}b_{|C_{-}|-1}$ is a linear extension of $N_{-}$, so $((N_{+},\preceq),(N_{-},\preceq),\preceq_{A},\preceq_{B})$ is an extended bipartition of $P^{*}-r$.

Conversely, given an extended bipartition $(N_{+},N_{-},a_{1}\preceq_{A}...\preceq_{A}a_{|N_{+}|},b_{1}\preceq_{B}...
\preceq_{B}b_{|N_{-}|})$, define sets $m_{1}^{+}=\emptyset$, $m_{1}^{-}=\emptyset$, $m_{i}^{+}=\min(\cup_{j=1}^{i-1}a_{|N_{+}|+1-j})$ for $2\leq i\leq|N_{+}|+1$ and $m_{i}^{-}=\min(\cup_{j=1}^{i-1}b_{|N_{-}|+1-j})$ for $2\leq i\leq|N_{-}|+1$. Define $J_{i}^{\sigma}$ to be the filter with minimal elements $m_{i}^{\sigma}$ for $2\leq i\leq|N_{\sigma}|+1$ and let $J_{1}^{\sigma}=\emptyset$. Let $C_{\sigma}=J_{1}^{\sigma}\subsetneq...\subsetneq J_{|N_{\sigma}|+1}^{\sigma}$. Then $(C_{+},C_{-})$ is a non-interfering pair with $|C_{+}|+|C_{-}|=|N_{+}|+|N_{-}|+2=d+1$, and this map from the set of extended bipartitions to the set of non-interfering pairs of chains is an inverse of the mapping of the previous paragraphs.

It remains to verify the runtime of computing the non-interfering pair of chains we constructed above. Without loss of generality, we focus on $J_{i}^{+}$. Filter $J_{1}^{+}=\emptyset$ and $J_{2}^{+}$ is the set of elements with a 1 in row $|N_{+}|$ of matrix $M$, computed in time $O(d)$. Now, suppose we have computed $J_{i}^{+}$ and want to compute $J_{i+1}$. By comparing rows $|N_{+}|+1-i$ and $|N_{+}|+2-i$ of $M$, we can compute the set $p_{i}$ of parents of $a_{|N_{+}|+1-i}$ that are not parents of $a_{|N_{+}|+2-i}$ (we include $a_{|N_{+}|+1-i}\in p_{i}$) in time $O(d)$. Note that $p_{i}=J_{i+1}-J_{i}$. Then $J_{i+1}^{+}=J_{i}^{+}\sqcup p_{i}$ where $\sqcup$ is disjoint union. Thus each filter of $J_{1}^{+}\subsetneq\ldots\subsetneq J_{|N_{+}|+1}^{+}$ can be computed in time $O(d)$, taking time $O(d^{2})$ overall.
∎

The problem is now reduced to uniformly sampling an extended bipartition. Constructing such a sampler is the last technical step in our argument.

###### Lemma 3.14 .

Given poset $(P,\preceq)$ of size $|P|=d$, there is an algorithm to uniformly sample an extended bipartition of $P$ in time $O(d^{2})$.

###### Proof.

We start by reformulating the matrix $M$ associated with $P$ (Definition 2.7) as a more suitable data structure $G_{P}$: iterate through the matrix $M$ and, for each element $v$, construct a list $p_{v}$ of its parent elements and a list $c_{v}$ of its child elements. This takes a single $O(d^{2})$ pass through $M$. Note that $G_{P}$ enables us to compute a maximal element in time $O(d)$ by starting at any node and following parent pointers.

Our algorithm, $\mathcal{A}$, receives a $G_{P}$ representation of a poset $P$ and uses recursion as follows. At each step, compute maximal element $v\in P$ in $O(d)$ and then construct $G_{P-v}$ from $G_{P}$ by deleting $v$ and the associated parent pointers from its children in time $O(d)$. Then compute $\mathcal{A}(G_{P-v})$ to obtain extended bipartition $((A,\preceq),(B,\preceq),\preceq_{A},\preceq_{B})$ of $P-v$. We will use this extended bipartition of $P-v$ to construct one for $P$. Note that $\preceq_{A}$ and $\preceq_{B}$ can be represented by increasing ordered lists of elements of $A$ and $B$ respectively.

Let $a_{j}$ be the $\preceq_{A}$-largest element that is $\preceq$-smaller than $v$ in $a_{1}\preceq_{A}\cdots\preceq_{A}a_{k}$. To find $a_{j}$, iterate from right to left (i.e., $\preceq_{A}$-largest to $\preceq_{A}$-smallest) over the $\preceq_{A}$ list and check whether
the current node $w$ has the property that $M_{w,v}=1$, stopping when the first child of $v$ is found. Define $b_{j^{\prime}}$ similarly. Then modifying $\preceq_{A}$ by inserting $v$ anywhere to the right of $a_{j}$ in $a_{1}\preceq\cdots\preceq a_{k}$ produces a linear extension $\preceq_{A^{\prime}}$ and the extended bipartition $((A\cup\{v\},\preceq),(B,\preceq),\preceq_{A^{\prime}},\preceq_{B})$ of $P$. We call the set of all such insertion points the valid placements for $A$, and define the valid placements for $B$ similarly. Let $L$ be the union of the valid placements for $A$ and $B$. By the above, computing $L$ and uniformly sampling a valid placement takes time $O(d)$. Finally, inserting $v$ into a linear extension takes time $O(d)$ assuming the linear extensions are implemented using linked lists. Overall, we do $O(d)$ work at each recursive step.

In the base case that $|P|=1$, we flip a coin to either return $((P,\emptyset),\preceq_{P},\preceq_{\emptyset})$ or $((\emptyset,P),\preceq_{\emptyset},\preceq_{P})$ where $\preceq_{P}$ and $\preceq_{\emptyset}$ are trivial linear extensions. Since we do $O(d)$ work at each recursive step and there are $|P|=d$ steps, the total run time is $O(d^{2})$.

It remains to verify that the sampling is uniform. For any extended bipartition of $(P,\preceq)$ given by ${((A,\preceq),(B,\preceq),\preceq_{A},\preceq_{B})}$, removing maximal $v$ yields a smaller extended bipartition of the sub-poset $(P-v,\preceq)$ such that if $a_{j}$ and $b_{j^{\prime}}$ are defined with respect to the smaller extended bipartition, then $v$ is either to the right of $a_{j}$ in $\preceq_{A}$ of $A$ or to the right of $b_{j^{\prime}}$ in $\preceq_{B}$ of $B$.
∎

Having sampled an extended bipartition, Lemma 3.13 already verified that we can convert it to a non-interfering pair of chains efficiently, and Lemma 3.11 shows how to map that to a simplex in the double order polytope in time $O(d^{2})$. Sampling the simplex takes time $O(d\log(d))$ (Lemma 3.6), so putting these steps together yields the overall sampler. Pseudocode appears in Algorithm 1.

###### Theorem 3.15 .

The poset ball for $(P^{*},\preceq)$ can be sampled in time $O(d^{2})$.

Figure: Algorithm 1 Poset Ball Sampler

###### Lemma 3.6 .

###### Definition 3.7 .

###### Definition 3.8 ( [ 2 ] ) .

###### Lemma 3.9 (Theorem 4.3 [ 2 ] ) .

###### Definition 3.10 ( [ 2 ] ) .

###### Lemma 3.11 ( Chappell et al. [ 2 ] ) .

###### Definition 3.12 .

###### Lemma 3.13 .

###### Proof.

###### Lemma 3.14 .

###### Proof.

###### Theorem 3.15 .

### 3.3 Rejection Sampling the Poset Ball Is Inefficient

We complement our efficient sampler with a negative result for rejection sampling the poset ball using any $\ell_{p}$ ball. First, the best possible candidate for rejection sampling is the $\ell_{\infty}$ ball.

###### Lemma 3.16 .

The unit $\ell_{\infty}$ ball $B_{\infty}^{d}$ is the minimum volume $\ell_{p}$ ball containing the poset ball.

###### Proof.

Any $\ell_{p}$ ball that contains $(1,..,1)$ must also contain all points in $\{0,1\}^{d}-\{(1,...,1)\}$ since each of these other points has strictly smaller $\ell_{p}$ norm. In particular, any $\ell_{p}$ ball that contains $(1,...,1)$ must contain $B_{\infty}^{d}$. Since the poset ball contains $(1,\ldots,1)$, the claim follows.
∎

Our overall result thus needs only to analyze rejection sampling from $B_{\infty}^{d}$.

###### Theorem 3.17 .

Rejection sampling the poset ball using any $\ell_{p}$ ball is inefficient.

###### Proof.

By Lemma 3.16, it suffices to consider $B_{\infty}^{d}$. Consider the poset $(P,\preceq)$ on $\{r,p_{1},\ldots,p_{d-1}\}$ with set of relations $\{p_{i}\preceq r\}_{i=1}^{d-1}$. Then for any other poset $P^{\prime}$, its poset ball has smaller volume as $R(P)\subset R(P^{\prime})$ means that $P^{\prime}$ can be formed from $P$ by intersecting $P$ with half-spaces defined by the relations corresponding to the relations in $R(P^{\prime})-R(P)$. Then $P$’s poset ball is a cylinder with bases $[0,1]^{d-1}$ and height 2 (in the direction of the root axis) so has volume $1^{d-1}(2)=2$. However, $|B_{\infty}^{d}|=2^{d}$. It follows that rejection sampling requires $\Omega(2^{d})$ samples from $B_{\infty}^{d}$ in expectation.
∎

###### Lemma 3.16 .

###### Proof.

###### Theorem 3.17 .

###### Proof.

## 4 Experiments

This section evaluates our $K$-norm mechanism on a variety of poset structures (for experiment code, see Github []). First, we derive a general result about the squared expected $\ell_{2}$ norm of $\ell_{p}$ balls (Section 4.1). Based on this result, the strongest comparison for our algorithm is the $\ell_{\infty}$ mechanism, and we take it as the baseline for our experiments on synthetic random posets (Section 4.2) and the real National Health Interview Survey [] (Section 4.3).

Note that our mechanism augments a given $d$-element poset with a root to ensure 2.8 as necessary. Since the baseline $\ell_{\infty}$ mechanism is applied to the $d$-dimensional problem, we ignore the root dimension of the $(d+1)$-dimensional noise vector produced by our mechanism when comparing squared $\ell_{2}$ norms. As discussed in Section 2.2, by post-processing, this does not affect privacy.

### 4.1 Choice of Baseline

This section justifies our choice of the $\ell_{\infty}$ mechanism — i.e., the $K$-norm mechanism instantiated with the $\ell_{\infty}$ norm — as the baseline in our experiments. This choice relies on the following result, proved in Appendix B.

###### Lemma 4.1 .

Let $\mathbb{E}_{2}^{2}(X)$ denote the expected squared $\ell_{2}$ norm of a uniform sample from $X$, and let $B_{p}^{d}$ denote the $d$-dimensional unit $\ell_{p}$ ball. Then $\mathbb{E}_{2}^{2}(B_{p}^{d})=\frac{d}{3}\left(\frac{3d}{d+2}\right)\left(
\frac{\Gamma(\frac{d}{p})\Gamma(\frac{3}{p})}{\Gamma(\frac{1}{p})\Gamma(\frac{
d+2}{p})}\right)$, where $\Gamma$ is the gamma function, and $\mathbb{E}_{2}^{2}(B_{\infty}^{d})=d/3$. Let $r_{p,d}=d^{1/p}$ be the minimum radius for which $r_{p,d}B_{p}^{d}$ contains $\mathcal{Y}(P^{*})$. By the above, $\mathbb{E}_{2}^{2}(r_{p,d}B_{p}^{d})=r_{p,d}^{2}\mathbb{E}_{2}^{2}(B_{p}^{d})$.

Figure: Figure 1: $r_{p,d}^{2}\mathbb{E}_{2}^{2}(B_{p}^{d})$ (see Lemma 4.1).
Refer to caption: x1.png

Remark 4.2 from Hardt and Talwar [] establishes that, fixing privacy parameters, the expected squared $\ell_{2}$ norm of a sample from the $K$-norm mechanism is proportional to the expected squared $\ell_{2}$ norm of its norm ball. Thus, to identify the best $\ell_{p}$-norm mechanism, it suffices to identify the $p$ minimizing $\mathbb{E}_{2}^{2}(r_{p,d}B_{p}^{d})$ in Lemma 4.1.

Figure 1 plots the analytic expression derived in Lemma 4.1 for various $p$ and $d$ and leads us to take the $\ell_{\infty}$-norm mechanism as the strongest baseline. We note briefly that Laplace ($\ell_{1}$) noise is approximately 2 ($d=2$) to 5 ($d=50$) times worse than $\ell_{\infty}$ noise by squared $\ell_{2}$ norm, so the following results are even stronger when evaluated against the Laplace mechanism.

###### Lemma 4.1 .

### 4.2 Random Posets

Our first set of experiments features random posets. The posets are generated using the algorithm given by Melançon et al. [] for uniformly sampling a directed acyclic graph on a fixed number of uniquely labeled vertices. As their algorithm has runtime $O(d^{4})$, we restrict attention to relatively small values for the number of poset elements $d$.

The first random poset experiment examines our algorithm’s improvement over the $\ell_{\infty}$ mechanism as $d$ grows. Figure 2 demonstrates that our algorithm’s advantage in terms of expected squared $\ell_{2}$ norm widens with $d$, increasing to over $90\%$ at $d=40$.

Figure: Figure 2: Each point records the average mean squared $\ell_{2}$ norm ratio between the poset and $\ell_{\infty}$ balls over 100 trials. A lower value means our mechanism achieves lower error.
Refer to caption: x2.png

The second and third random poset experiments break this data out along two dimensions (Figure 3). Fixing $d=10$ (ignoring the root), we plot improvement as a function of both the depth (longest chain of relations) and number of relations in the poset. Both numbers are computed on the transitive reduction of the directed acyclic graph corresponding to the poset, i.e., the directed acyclic graph that minimizes the number of edges while preserving all paths of the poset. As observed for $d$, at a high level we find that larger and richer poset structures lead to correspondingly more dramatic improvements, up to a 4x reduction in error.

Figure: Figure 3: Each point records the average mean squared $\ell_{2}$ norm ratio between the poset and $\ell_{\infty}$ balls over at least 100 trials. We omit extremes of both depth and number of edges, as they do not occur enough times in our overall sample of 5000 random posets to cross the 100-sample threshold.
Refer to caption: x3.png

### 4.3 National Health Interview Survey

The second set of experiments uses the National Health Interview Survey (NHIS) []. As described in the introduction, the survey includes or omits certain questions depending on previous answers. This induces a poset, and our experiments use either the first, first two, or first three sections of the survey (Hypertension, Cholesterol, and Asthma). The resulting posets have size from $d=4$ to $d=15$. As shown in Figure 4, our mechanism more than halves the error of the baseline mechanism in each setting.

Figure: Figure 4: NHIS average mean squared $\ell_{2}$ norm ratios, from 10,000 trials each.

We note that, in a departure from the random poset experiments, here our mechanism’s advantage remains fairly constant as $d$ grows. This may be a consequence of the NHIS’s shallow poset structure: it contains only one chain of more than two relations (the first three questions in the Hypertension section), and as demonstrated in Figure 3, our mechanism’s advantage grows with poset depth.

## 5 Discussion

The material above demonstrates that the $K$-norm mechanism offers strong utility improvements over existing pure differentially private mechanisms for privately counting partially ordered data without sacrificing efficiency. A natural direction for future work is to consider the same problem under approximate differential privacy. There, elliptic Gaussian noise is the primary tool, and the geometric problem changes from sampling the induced norm ball to computing the “smallest” (in terms of expected squared $\ell_{2}$ norm) ellipse enclosing the induced norm ball. Unfortunately, while Joseph and Yu [] solved this problem for count and vote, their solutions relied on the norm balls being symmetric around the vector $(1,\ldots,1)$, and this does not hold for the poset ball in general. This suggests that new techniques may be required to obtain a similar result for partially ordered data.

## Appendix A Sampler Proofs

###### Remark A.1 .

The exposition from Chappell et al. [] defines the double order polytope of a double poset $(P,\preceq_{+},\preceq_{-})$ as $\mathcal{O}(2P_{+})\boxminus\mathcal{O}(2P_{-})$, defines the double chain polytope as $\mathcal{C}(2P_{+})\boxminus\mathcal{C}(2P_{-})$ and
for a pair of chains $C=(C_{+},C_{-})$ it defines $\bar{F}(C)=2F(C_{+})\boxminus 2F(C_{-})$, and $\bar{F^{\prime}}(C)=2F^{\prime}(C_{+})\boxminus 2F^{\prime}(C_{-})$. Removing these factors of 2 from the definitions does not change the combinatorial structure of the double order polytope or double chain polytope since this removal simply scales down the $(d-1)$ dimensions of $\mathbb{R}^{d}$ that excludes the dimension that is added from the $\boxminus$ operation. Consequently, the triangulation of lemma 3.11 still holds. The reason we remove the factors of 2 is because the sensitivity space we are interested in is $CH(\mathcal{O}(P^{*})\cup-\mathcal{O}(P^{*}))$ which is equivalent to our definition of the double order polytope $\mathcal{O}_{2}(P^{*}-r)$ where $r$ is the global maximum of $P$.

See 3.5

###### Proof.

We have $V(CH(\mathcal{P}^{\prime}\cup-\mathcal{P}^{\prime}))=V(CH(V(\mathcal{P}^{
\prime})\cup V(-\mathcal{P}^{\prime})))\subseteq V(\mathcal{P}^{\prime})\cup V
(-\mathcal{P}^{\prime})=V(\mathcal{\mathcal{P}})\cup V(-\mathcal{P})\cup\{0\}$ where the $\subseteq$ comes from the fact that the vertices of the convex hull of a finite set is a subset of that set. Since $CH(\mathcal{P}^{\prime}\cup-\mathcal{P}^{\prime})$ has antipodal symmetry, then $x\in CH(\mathcal{P}^{\prime}\cup-\mathcal{P}^{\prime})$ implies $-x\in CH(\mathcal{P}^{\prime}\cup-\mathcal{P}^{\prime})$ which means that the line segment between $x$ and $-x$ contains a small 1-dim neighborhood $B$ around the origin such that $B\subset CH(\mathcal{P}^{\prime}\cup-\mathcal{P}^{\prime})$, so the origin is not a vertex of $CH(\mathcal{P}^{\prime}\cup-\mathcal{P}^{\prime})$, so we have that $V(CH(\mathcal{P}^{\prime}\cup-\mathcal{P}^{\prime}))\subset V(\mathcal{P})\cup
V
(-\mathcal{P})$.

Now, suppose that $v\in V(\mathcal{P})$ is not a vertex of $CH(\mathcal{P}^{\prime}\cup-\mathcal{P}^{\prime})$. We call a convex combination of vertices non-singleton if its support contains at least 2 vertices. The supposition implies there is a non-singleton convex combination of vertices in $V(\mathcal{P}^{\prime})\cup V(-\mathcal{P}^{\prime})$ that equals $v$. None of vertices in the support of this combination can lie in $V(-\mathcal{P}^{\prime})$ because then the $x_{1}$ coordinate of the combination would be less than 1 whereas the first coordinate of $v$ is 1. So $v$ must be a non-singleton convex combination of points in $V(\mathcal{P})$, contradicting the fact that $v$ is a vertex of $V(\mathcal{P})$. So $V(\mathcal{P})\subset V(CH(\mathcal{P}^{\prime}\cup-\mathcal{P}^{\prime}))$ and similarly $V(-\mathcal{P})\subset V(CH(\mathcal{P}^{\prime}\cup-\mathcal{P}^{\prime}))$. But by the previous paragraph, $V(CH(\mathcal{P}^{\prime}\cup-\mathcal{P}^{\prime}))\subset V(\mathcal{P})\cup
V
(-\mathcal{P})$, so $V(CH(\mathcal{P}^{\prime}\cup-\mathcal{P}^{\prime}))=V(\mathcal{P})\cup V(-
\mathcal{P})$.
∎

###### Remark A.1 .

###### Proof.

## Appendix B Experiment Proofs

We start with a simple result about the expected squared $\ell_{2}$ norm, $\mathbb{E}_{2}^{2}$. Recall from Section 4.1 that $\mathbb{E}_{2}^{2}(X)$ denotes the expected squared $\ell_{2}$ norm of a uniform sample from $X$.

###### Lemma B.1 .

Then $\mathbb{E}_{2}^{2}(X\oplus Y)=\mathbb{E}_{2}^{2}(X)+\mathbb{E}_{2}^{2}(Y)$.

###### Proof.

To uniformly sample $X\oplus Y$, we can uniformly sample $x\in X,y\in Y$ and then return $x\oplus y$. Samples $x$ and $y$ embed into disjoint coordinates of $x\oplus y$, so $\|x\oplus y\|_{2}^{2}=\|x\|_{2}^{2}+\|y\|_{2}^{2}$.
∎

See 4.1

###### Proof.

We use the fact that $\int_{0}^{1}t^{a-1}(1-t)^{b-1}=\frac{\Gamma(a)\Gamma(b)}{\Gamma(a+b)}$. Then

$$ $\displaystyle\mathbb{E}_{2}^{2}(B_{p}^{d})$ $\displaystyle=|B_{p}^{d}|^{-1}\int_{|x_{1}|^{p}+...+|x_{d}|^{p}\leq 1}\sum_{i= 1}^{d}x_{i}^{2}\partial x_{1}...\partial x_{d}$ $\displaystyle=|B_{p}^{d}|^{-1}\int_{|x_{1}|^{p}+...+|x_{d}|^{p}\leq 1}dx_{1}^{ 2}\partial x_{1}...\partial x_{d}$ $\displaystyle=|B_{p}^{d}|^{-1}\int_{-1}^{1}dx_{1}^{2}\partial x_{1}\int_{|x_{2 }|^{p}+...+|x_{d}|^{p}\leq 1-|x_{1}|^{p}}\partial x_{2}...\partial x_{d}$ $\displaystyle=|B_{p}^{d}|^{-1}\int_{-1}^{1}dx_{1}^{2}|B_{p}^{d-1}|(1-|x_{1}|^{ p})^{\frac{d-1}{p}}\partial x_{1}$ $\displaystyle=2d|B_{p}^{d}|^{-1}|B_{p}^{d-1}|\int_{0}^{1}x^{2}(1-x^{p})^{\frac {d-1}{p}}\partial x.$ $$

We substitute $y=x^{p}$ to get

$$ $\displaystyle\partial y$ $\displaystyle=px^{p-1}\partial x$ $\displaystyle\partial x$ $\displaystyle=\frac{1}{px^{p-1}}\partial y$ $\displaystyle\partial x$ $\displaystyle=\left(\frac{1}{p}\right)y^{\frac{1}{p}-1}\partial y$ $$

and the chain of equalities continues with

$$ $\displaystyle\mathbb{E}_{2}^{2}(B_{p}^{d})$ $\displaystyle=\left(\frac{2}{3}\right)d|B_{p}^{d}|^{-1}|B_{p}^{d-1}|\int_{0}^{ 1}y^{\frac{2}{p}}(1-y)^{\frac{d-1}{p}}\left(\frac{3}{p}\right)y^{\frac{1}{p}-1 }\partial y$ $\displaystyle=\left(\frac{2}{3}\right)d|B_{p}^{d}|^{-1}|B_{p}^{d-1}|\left( \frac{3}{p}\right)\int_{0}^{1}y^{\frac{3}{p}-1}(1-y)^{\frac{d-1}{p}}\partial y$ $\displaystyle=\left(\frac{2}{3}\right)d|B_{p}^{d}|^{-1}|B_{p}^{d-1}|\left( \frac{3}{p}\right)\left(\frac{\Gamma\left(\frac{3}{p}\right)\Gamma(\frac{d-1}{ p}+1)}{\Gamma(\frac{d+2}{p}+1)}\right)$ $\displaystyle=\left(\frac{2}{3}\right)d\left(\frac{(2\Gamma(\frac{1}{p}+1))^{d -1}}{\Gamma(\frac{d-1}{p}+1)}\right)\left(\frac{\Gamma(\frac{d}{p}+1)}{(2 \Gamma(\frac{1}{p}+1))^{d}}\right)\left(\frac{\Gamma(\frac{3}{p}+1)\Gamma( \frac{d-1}{p}+1)}{\Gamma(\frac{d+2}{p}+1)}\right)$ $\displaystyle=\left(\frac{2}{3}\right)d\left(\frac{\Gamma(\frac{d}{p}+1)}{2 \Gamma(\frac{1}{p}+1)}\right)\left(\frac{\Gamma(\frac{3}{p}+1)}{\Gamma(\frac{d +2}{p}+1)}\right)$ $\displaystyle=\frac{d}{3}\left(\frac{3d}{d+2}\right)\left(\frac{\Gamma(\frac{d }{p})\Gamma\left(\frac{3}{p}\right)}{\Gamma(\frac{1}{p})\Gamma(\frac{d+2}{p})} \right).$ $$

For $p=\infty$, we use

$$ $\displaystyle\mathbb{E}_{2}^{2}(B_{\infty}^{d})=\mathbb{E}_{2}^{2}([0,1]^{d})= d\mathbb{E}_{2}^{2}([0,1])=d\int_{0}^{1}t^{2}dt=\frac{d}{3}$ $$

where the first equality comes from the fact that the expectation restricted to the positive orthant does not change the expectation value because of symmetry over the orthants, and the second equality comes from Lemma B.1.

We show that $r_{p,d}=d^{1/p}$. Note that $r_{p,d}$ is equal to the smallest radius such that $r_{p,d}B_{p}^{d}$ contains the point $(1,...,1)\in\mathcal{Y}(P^{*})$ because if $(1,...,1)\in r_{p,d}B_{p}^{d}$ then all other binary vectors of length $d$ are also contained in $r_{p,d}B_{p}^{d}$, i.e. $\mathcal{Y}(P^{*})\subset r_{p,d}B_{p}^{d}$.

Next, we show that $\mathbb{E}_{2}^{2}(r_{p,d}B_{p}^{d})=r_{p,d}^{2}\mathbb{E}_{2}^{2}(B_{p}^{d})$. Since $r_{p,d}B_{p}^{d}=\{r_{p,d}x:x\in B_{p}^{d}\}$,

$$ $\displaystyle\mathbb{E}_{2}^{2}(r_{p,d}B_{p}^{d})$ $\displaystyle=|B_{p}^{d}|^{-1}\int_{|x_{1}|^{p}+...+|x_{d}|^{p}\leq 1}\sum_{i= 1}^{d}(r_{p,d}x_{i})^{2}\partial x_{1}...\partial x_{d}$ $\displaystyle=r_{p,d}^{2}|B_{p}^{d}|^{-1}\int_{|x_{1}|^{p}+...+|x_{d}|^{p}\leq 1 }\sum_{i=1}^{d}x_{i}^{2}\partial x_{1}...\partial x_{d}$ $\displaystyle=r_{p,d}^{2}\mathbb{E}_{2}^{2}(B_{p}^{d}).$ $$

∎

###### Lemma B.1 .

###### Proof.

###### Proof.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: How can the algorithm be adapted to approximate DP and achieve better results than pure DP?
soundness: 3
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.
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.
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.

---

confidence: 2
contribution: 3
initial_rating: 5
presentation: 1
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?
soundness: 3
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)$.
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.
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.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 2
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.
soundness: 3
strengths: - Brings in tools from another research area to improve algorithms/bounds for a natural and practical problem
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.
weaknesses: - The paper is difficult to read for someone who is not an expert in partial orders.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
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.
soundness: 2
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.
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.
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.)

Meta-review: 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.

Decision: Accept (Poster)