Privately Counting Partially Ordered Data
Authors: Matthew Joseph
Mónica Ribero
Alexander Yu
Venue: ICLR 2025 Poster (2025)
Keywords: differential privacy
Primary area: alignment, fairness, safety, privacy, and societal considerations

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.

Published as a conference paper at ICLR 2025
PRIVATELY COUNTING PARTIALLY ORDERED DATA
Matthew Joseph, Mónica Ribero & Alexander Yu Google Research NY
ABSTRACT
We consider differentially private counting when each data point consists of d bits satisfying a partial order. Our main technical contribution problem-specific K K-norm mechanism that runs in time (d2)) 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.
INTRODUCTION
A differentially private (DP) (Dwork et al., 2006) 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 &p sensitivity: if the statistic T' is vector in Rá adding a user's data point must not change the ép norm T by more than Ap. This framework generic enough to apply to wide variety of problems, but it can yield relatively poor performance for statistics whose sensitivity is not tightly characterized by an lp norm. One such statistic is counting on partially ordered data.
As straightforward running example, the National Health Interview Survey (Services & Medicaid, 2024) has been administered annually since 1957 by the Center for Disease Control. The Hyper- tension 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 answer "yes" to the second: equivalently, if the answers are given as binary vector x, the survey structure imposes partial order 22 S Ø1- A count 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.
is possible to apply lp sensitivity to partially ordered data. In the survey example, a respondent answer "yes" to every question, so the vector of counts has & 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 0) or 1.......). In this sense, straightforward application of Laplace (or other Ep mechanism) noise may be "loose".
1.1 CONTRIBUTIONS
Our main technical contribution is an efficient implementation of the K noomm mechanism (Hardt & Talwar, 2010) for counting partially ordered data. Our solution be applied to any partial order, satisfics pure differential privacy, and runs in time (d²) (Theorem 3.15). This provides a more than cubic speedup
the fastest general polytope sampler and is provably exponentially faster than any &, 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 & Yu (2024) previously constructed efficient implementations of the K-norm mechanism to obtain better noise distributions for the problems of Econtribution-boundee For longer discussion of the K-norm mechanism, its variants, and its relation to other query- answering solutions like the projection (Nikolov et al., 2013; Nikolov, 2023), matrix (Li et al.,
sum, count, and vote.
mtjoseph, mrihero, alexjyu ) google..comm

---

Published as a conference paper at ICLR 2025
2015: McKenna et al., 2018), and factorization (Edmonds et al., 2020; Nikolov & Tang, 2023) mechanisms, we refer the interested reader to their paper; here, we note that these mechanisms can be viewed general but possibly slow approximations of optimal constructions of problem-specifie 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 & Yu (2024) is that consider differ- ent problems that require different sampling techniques. more detail, these different problems are characterized by different combinatorial objects. In Joseph & Yu (2024), their sum and vote poly- topes are based on a truncated hypercube and permutohedron, respectively. Here, the poset polytope most closely related 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 & Yu (2024), 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. (2006).. Databases X, X' from data domain X are neighbors X ~ X they differ in the presence or absence of single record. A randomized mechanism M X' - O is e-differentially private (DP) for all X ~ X' E X and any S S O,
PM (MX) S (M(MM((()) S).
Our solution will apply the K-norm mechanism.
Lemma 2.2 (Hardt & Talwar (2010)). Given statistic T with || w -|-sensittivity A and database X, the
K-norm mechanism has outpul density (x( x exp (- Ily T(X)Il) and satisfies e-DP.
We apply an instance of the K-norm mechanism chosen using our statistic's ' sensitivity space. Definition 2.3 (Kattis & Nikolov (2017); Awan & Slavković (2021)). The sensitivity space of statistic S(T) (T(X) - T(X') X, X' 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 E Rd, there exists c > O such that cW), and symmetric around (u= W + -u W), then the function || -Ilw: Rd Rzo
given by || ||w = inf E Rzo u E cW} is norm, and we say W induces -|w.. Definition 2.5. statistic T has a sensitivity space convex hull CS(S(T)) satisfying Lemma 2.4, we say T induces a norm, and call CH(S()) the induced norm ball of
Awan & Slavkovié (2021) show that the instance of the K-norm mechanism using statistic's in- duced 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 & Talwar (2010). Running the K Knnor mechanism reduces to sampling the unit ball for the norm -1-
Our main technical contribution is therefore fast sampler for the induced norm ball for counting partially ordered data. This is d-dimensional polytope with 2(d) constraints. Applying the best general sampler takes time ((d2+=) where 2 2 is the matrix multiplication exponent (Theorem 1.5 of Laddha et al. (2020)). and achieving a close enough approximation for (ee)-DP adds another (d) factor (Appendix A of Hardt & Talwar (2010)).
2.2 PARTIALLY ORDERED DATA
Throughout, we assume that our goal is to compute a sum T(X) = Erex x of length-d binary vectors with bits that satisfy a partial order.
2

---

Published as a conference paper at ICLR 2025
Definition 2.7. A partially ordered set poset (P. is a finite set P together with a reflexive,
transitive, and anti anti-symmetric relation 3. If PL.P2 E P and P1 I P2. we say that p1 is a child of P2 and P2 is a parent of pt. A linear extension of poset (P, 3) is total ordering (P. that
- Pa such that P; 3 Pj implies i <. j. We assume that poset is given in the form of a [P] |P| binary matrix M where Mij = 1 + 3 Pj. We say a length- P| binary vector æ is partially ordered if I Pj implies x; S Zz.
preserves 3, Le. an ordering of the elements of P given by pt 3 P2 3
We also assume that each poset has single root.
Assumption 2.8. The poset (P. 3) has a root r E P such that p I r for all p p P.
For surveys, this corresponds 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 deseribed by Awan & Slavković (2021). Note also that if root, we can simply add a root, apply our mechanism, and ignore the added dimension in the final output, done in our experiments. By post-processing, this does not alter the privacy guarantee.
instead given poset without
3 AN EFFICIENT MECHANISM
We start with high level summary of the sampler. Since our goal is to sample the norm ball in- duced by our statistic, we first show that counting partially ordered data induces a norm, and that the induced norm ball can be expressed (Section 3.1). This connection allows us to leverage a triangulation for double order polytopes de- veloped by Chappell et al. (2017). The problem then reduces to sampling single simplex from the triangulation. However, the simplices in this triangulation are indexed by pairs of non-interfering chains (Definition 3.10) - essentially disjoint sets of elements in the poset ground set with a special structure given by the order relation and it is not obvious how to sample such an object uniformly random. To do so, we prove a bijection between the pairs of -on-interfering chains of the trian- gulation and a family of new structures called extended bipartitions (Definition 3.12), for which we construct a uniform sampler (Section 3.3). Putting these elements together yields an overall sampler of simplex of the triangulation, from which we can easily sample a single point (Section 3.4).
combinatorial object called double order polytope
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 Assumption 2.8 that we assume the poset (P*, =) ordering our data points has a root such that IT r for all p E p"; we omit this assumption for the rest of this section.
Lemma 3.1. Let ((p- (X) = =xrex be a statistic summing data points x that satisfy a partial order (P*, 3) (Definition 2.7). Then T(p",z) induces a norm.
Proof. We verify the conditions in Lemma 2.4. We write T = T(p for brevity.
CH(S(T)) is a convex hull and so immediately convex. Let ((CH()(T)) be the set of vertices of (STT) By the definition of sensitivity space, the vertices of (S(T) are the length- [P*] partially ordered binary vectors and their negations. There are finitely many vertices, so CS(SS))) bounded. Any point p E (STS(T)
a convex combination of the vertices Eey,, and ws V(CH(S(TT)) implies -U; E V(CH(S(TT)) so -p = Ea(-v:) E CH(SS))). Thus, (S(T) is symmetric around the origin.
It remains to show CH(S(T)) is absorbing. Consider any linear extension (P*, of (P*, ). Then (P*, 3') has all of the relations in (P*, 3). so (()) C S(T 22).. and C (C((S(((P
(S(((((P
Define {ui...., v2) } to be the set of binary vectors where vs is the vector whose first entries are while the rest are O. Then ((CH(S(()P. (#U),..,, tua). Since (ui,.., faa forms basis of Rdd there is an invertible linear map map- ping (ui..., va to the standard basis. In particular, (SCH(S(((P is the unit e, ball By. Let b be small origin centered ball around O in Bd. Then A A-1(b) is small origin
is
3

---

Published as a conference paper at ICLR 2025
(1,1)
(-1,-1)
The solid orange border outlines the d = 2 path graph (02 S x1) poset ball. The dashed teal border is the minimum containing & ball, and the dotted purple border is the minimum contain- ing foo ball.
Figure I:
centered ellipsoid in (H((((((P 21))) ie. 0 is an interior point of (H()(T(p= Since ((T(P))))) C ((T it follows that (H(((((P). is absorbing.
We shorthand T's induced norm ball the poset ball. As simple example, the poset ball for the path graph 22 S appears in Figure 1. 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. (2017).
Reasoning about the double order polytope requires some additional definitions related to posets.
Definition 3.2. double poset is a triple (P.I+: 3-) where P+ = (P. 3+) and P- = 3-) posets on the same ground set. A double poset is compatible if P+ and P- have shared linear extension.
Definition 3.3 (Chappell et al. (2017)). Let Pi, P2 C Rd be polytopes. The Cayley sum P P2 is defined by Pi W P2 CHI(11 @ P ((-1) P2). Define Pi P2 = Pı B P2 The order polytope (P)) of poset (P, 3) is the set of all order preserving functions f + [0. such that 0 S (a) S f(b) for all a, b P where < b. The double order polytope O2(P) double poset (P. 3-) O(P+) (O(P.).
P1 and
We can now state the connection between the poset ball and double order polytope.
Lemma 3.4. The poset ball for poset (P*, is O2(p" - -r), the double order polytope on the double order poset (p*-r,3. 3).
Proof. Let be the set of functions f P {0, 1} such that S f(a) S f(b S for all a E P" where < b. We can view functions in S as P"I--dim binary vectors in the natural way. Recall that the poset ball is CH(S -S). Equivalently, is CH(O((")) U (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. (2017); for completeness, a proof appears in Appendix A.
Claim 3.5. Let P be (d - 1) dim convex polytope in Rd lying in the hyperplane I1 1. Let P' = PU= (0). Then V(CH - -P') V(P) UV(-))
By Claim 3.5, the vertices of CH(O(P))U-((P)) vertices in V(O(P*)) {0} are of the form 1 & v where v is a vertex of V(O and the first dimension corresponds to the r-dimension. In other words, the vertices of this shape are exactly the vertices of Oz(P* - r). the double order polytope on the double poset (P* r, r.
are V(O(P")) - (0). The
By Lemma 3.4, our new goal is to construct fast sampler for the double order polytope Oz PP* -r).
'This is slight modification of the definition of the double order polytope given by Chappell et al. (2017), but the change does not meaningfully affect the properties of this structure (see Remark A. for details).
4

---

Published as a conference paper at ICLR 2025
3.2 DOUBLE ORDER POLYTOPES AND DOUBLE CHAIN POLYTOPES
We sample O2(P* by constructing a triangulation that decomposes it into disjoint d-dimensional simplices of equal volume. By this construction, it suffices 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 simplex is folklore; we take the statement from Joseph & Yu (2024). Lemma 3.6. A collection of points Zu..... Id E R with n Z d are affinely independent if E 9,24 = O and Ei=o 04 O implies = 0. A d-simplex is the convex hull of d + 1 affinely independent points and can be uniformly sampled in time Old log(d).
Since sampling a simplex is easy, it remains to find triangulation of O2(P" - r) into simplices. For completeness, the following definition formalizes the notion of a triangulation.
Definition 3.7. Let P C R be a polytope. For 0 < S d 1, proper k-dim face P intersection I of the form H n 0P of a (d (d-110 1)-dim hyperplane H with the boundary of such that the I C ap and dim = k. A subdivision of P a collection of d-dim polytopes Pi...., Pm such that P = L P; and for each 1 S i < j S m the (possibly empty) set P. n. P3 is proper face of each of P; and Pj. A triangulation of is a subdivision containing only simplices. A simplex with vertices in lattice A is unimodular if it has minimal volume. A triangulation is unimodular if all of its simplices are unimodular.
P is an
We use a result from Chappell et al. (2017) that provides a mapping between the double order polytope and related geometric object, the double chain polytope.
Definition 3.8 (Chappell et al. (2017)). Given poset P, a chain is a sequence of (strictly) increasing elements in P. The chain polytope C(P) is the set of functions g: : P - R220 such that g(a1) + ... + g(ax) S 1 for all chains 01 1 ... 1 ak of P. The double chain polytope C2(P) of a double poset
(P. -. <-) is C(P+) FC((P)
Lemma 3.9 (Theorem 4.3 Chappell et al. (2017)). For any compatible double poset (P.
there is explicit homeomorphism between the double chain polytope C2) and the double order polytope (P).
Conveniently, the mapping transfers a triangulation of the double chain polytope to a triangulation of the double order polytope also due Chappell al. (2017). This triangulation will be indexed by objects called non-interfering pairs of chains.
Definition 3.10 (Chappell al. (2017)). Given poset (P, I C P is a filter if E I and x 1 y implies y E I, and the Birkhoff poset J(P) is the poset given by the filters of P ordered by inclusion. Given double poset (P, 3+, 3-), for chains of filters C+ C [(P+) and C_ C [P-)), we say the pair of chains C = (C+, C_) is non-interfering if min(J+) n min(J_) = 0 for all J+ C..J_ E C_., where min(.) denotes the set of minimal elements of the filter. Moreover, denote by (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. (2017).
Lemma 3.11 (Chappell et al. (2017)). Let (P, (P. be a double poset. For C (P)), define F(L) (H J
E L}) RIPI, For non-interfering pair of chains C = (C., C-) of size IP| +++1 1, define map F(C) = F(C+) E F(C.). Then (F(C) C E (P)) triangulation of O2(P) into Pl-dimensional simplices. Moreover, given C, F(C)
ICI = C+1
can be computed in time )
As 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.
3.3 EXTENDED BIPARTITIONS
Definition 3.12. Given poset (P.3). extended bipartition is quadruple where 1), are subposets of P such that A a B (A,
A = P. and 3A, IB are linear extensions of (A, 3), (B, =) respectively.
5

---

Published as a conference paper at ICLR 2025
At a high level, given 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 can define 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. Due to space constraints, the full proof of this result appears in Appendix A.
extended bipartition,
Lemma 3.13. There is bijection between the set ofn-innteeerni pairs of chains C' = (C+, C-) of the double poset (P* -T, 3, 3) of size |C| ci=ICa =IC+| + |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²).
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, 3) of size |P| = there is an algorithm to uniformly sample an extended bipartition of P in time (dP).
Proof. We start by reformulating the matrix M associated with P (Definition 2.7) as more suitable data structure Gp: iterate through the matrix M and, for each element v, construct a list p. of its parent elements and a list co of its child elements. This takes a single Odd)) pass through M. Note that Gp enables us to compute a maximal element in time (dd) by starting at any node and following parent pointers.
Our algorithm, A, receives a Gp representation of a poset P and uses recursion as follows. At each step, compute maximal element E P in O(d) and then construct Gr-v from Gp by deleting and the associated parent pointers from its children in time (d). Then compute p-p) to obtain extended bipartition ((A, 3) (B, 3), AA, 3B) of P v. We will use this extended bipartition of P - v to construct one for P. Note that A and <B can be represented by increasing ordered lists of elements of A and B respectively.
Let aj be the 3A -a-lest element that is smsmlleer than in a1 IA AA ag. To find ag, iterate from right to left (i.e., IA llrgest -m-sleeesst) over the 3A list and check whether the current node w has the property that Mare = 1, stopping when the first child of is found. Define by similarly. Then modifying 3A by inserting e anywhere to the right of a, in 01 I 2..._ ag produces a linear extension 3 A and the extended bipartition ((A J { 3), (B. 3). Ix. 3B) 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 (d). Finally, inserting v into a linear extension takes time (dd) assuming the linear extensions implemented using linked lists. Overall, we do Od) work at each recursive step.
In the base case that IP| where zp and Ze 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 Odd²).
flip coin to either return ((P,0),
-r, or ((0, P): Š0,
It remains to verify that the sampling is uniform. For any extended bipartition of (P, given by ((A, 3), (B, -), -A, In), removing maximal v yields smaller extended bipartition of the sub- poset (P - v, =) such that if a, and by are defined with respect to the smaller extended bipartition, then either the right of aj in IA of A to the right of by. in 3B of B.
3.4 OVERALL ALGORITHM
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 map that a simplex in the double order polytope in time (d2). Sampling the simplex takes time (d log(d) (Lemma 3.6), so putting these steps together yields the overall sampler. Pseudocode appears in Algorithm
Theorem 3.15. The poset ball for (P*, 3) can be sampled in time (dd).

---

Published as a conference paper at ICLR 2025
Algorithm Poset Ball Sampler
Input: Poset P satisfying Assumption 2.8
2: Uniformly sample an extended bipartition (N _, 3 3B) (Lemma 3.14)
3: Convert (N+, 3A 3B) into its non-interfering chain (C+, C-) (Lemma 3.13)
4: Compute the vertices of the simplex F(C) = F(C+) E F(C-) (Lemma 3.11)
5: Return a uniform sample from ((C) (Lemma 3.6)
3.5 REJECTION SAMPLING THE POSET BALL IS INEFFICIENT
We complement our efficient sampler with negative result for rejection sampling the poset ball using any ep ball. First, the best possible candidate for rejection sampling is the for ball.
Lemma 3.16. The unit fo ball B is the minimum volume lp ball containing the poset ball.
Proof. Any Ep ball that contains (1,...) must also contain all points in {0, 1-d- 1)} since each of these other points has strictly smaller Ep norm. In particular, any lp ball that contains (I,..., 1) must contain Bd Since the poset ball contains (I...., 1), the claim follows.
Our overall result thus needs only to analyze rejection sampling from B Theorem 3.17. Rejection sampling the poset ball using any En ball is inefficient.
Proof. By Lemma 3.16, it suffices to consider Bdd Consider the poset (P, =) on fT.PP.....PP Pd-1
with set of relations {p: I -d-1 |=1 Then for any other poset P', its poset ball has smaller volume as R(P) C R(P') means that can be formed from P by intersecting P with half-spaces defined by the relations corresponding to the relations in R R(P")) R(P). Then P's poset ball is a cylinder with bases [0, 1 d and height 2 (in the direction of the root axis) so has volume 1d-1(2) = 2. However,
B 2d. It follows that rejection sampling requires !2(24) samples from B in expectation. O
EXPERIMENTS
This section evaluates our K-norm mechanism on a variety of poset structures. First, we derive a general result about the squared expected & norm of lp balls (Section 4.1). Based on this result, the strongest comparison for our algorithm is the lo mechanism. We use this as the baseline for experiments on path posets, random posets (Section 4.3) and the National Health Interview Sur- vey (Services & Medicaid, 2024) (Section 4.4). An evaluation of runtime appears in Section 4.5.
Note that our mechanism augments given d-element poset with root ensure Assumption 2.8 as necessary. Since the baseline foo mechanism is applied to the d-dimensional problem, we ignore the root dimension of the (d+ (d+1)-dimen) -idmenssioall noise vector produced by our mechanism when comparing squared & 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 loo mechanism - i.e., the K-norm mechanism instantiated with the fxc norm - as the baseline our experiments. This choice relies on the following result, proved in Appendix B.
Lemma 4.1. Let E2(X) denote the expected squared E norm of a uniform sample from X, and let By denote the d-dimensional unit Ep ball. Then (3(B),
r(g)(())
where T is the gamma function, and (3(Ba)) d/3. Let Fp.d // / be the minimum radius for which a contains )(P"). By the above, (rp.a =3
3d
d=2
(()))())))
Remark 4.2 from Hardt Talwar (2010) establishes that, fixing privacy parameters, the expected squared &g norm of sample from the K-norm mechanism is proportional to the expected squared

---

Published as a conference paper at ICLR 2025
experted squared f norm
10a
2
10a
20 dimension
50
Figure 2: r2 Bg (Bx) (see Lemma 4.1).
le norm of its norm ball. Thus, to identify the best fp-norm mechanism, it suffices to identify the minimizing (r) in Lemma 4.1.
Figure plots the analytic expression derived in Lemma 4.1 for various p and d and leads us to take the loo -nom mechanism the strongest baseline.
We note briefly that Laplace (f1) noise is approximately 2 (d = 2) to 5 (d = 50) times worse than loo noise by squared & norm, the following results are even stronger when evaluated against the Laplace mechanism. Furthermore, for (1, -DP the analytical Gaussian mechanism (Balle & Wang, 2018) is also dominated by the lo mechanism experiments (see plot in Appendix B.2), so we omit here.
the range d 50 featured in our
4.2 PATH POSET
We start with the path poset defined by the ground set P = (1...., d} and the corresponding linear d (see Figure 1 for an illustration of its poset ball for d = 2). Figure demonstrates that our K-norm mechanism improves significantly over the baseline on the path poset, up over order of magnitude near d 50. As subsequent experiments will develop, this dramatic error reduction consequence the path graph's extreme depth. Informally, it is the graph on elements with the smallest poset ball, since any other graph can be created from the path graph by repeatedly moving the leaf element the original path and grafting somewhere higher up the tree, and this operation strictly decreases the number of relations in the poset.
order 1 3 <
0.7
poset nomitt. norm
0.6
0.5
0.2
0.1
10
20
30
40
50
depth
Figure 3: Each point records the average mean squared E, norm ratio between the poset and loo balls for the path graph over 100 trials for each of various
8

---

Published as a conference paper at ICLR 2025
4.3 RANDOM POSETS
The second set of experiments features random posets. The posets are generated using the algorithm given by Melançon al. (2001) for uniformly sampling directed acyclic graph fixed number of uniquely labeled vertices. As their algorithm has runtime O(d*), we restrict attention to relatively small values for the number poset elements d.
The first random poset experiment examines our algorithm's 's improvement over the too mechanism d grows. Figure 4 demonstrates that algorithm's advantage in terms of expected squared & norm widens with d, increasing to over 90% at d = 40.
0.8
poset poset normiz, nomm
0.6
0.5
0.4
0.3
0.1
10
15
20
25
30
35
40
Figure 4: Each point records the average mean squared lz norm ratio between the poset and &oc balls over 100 trials of random posets. A lower value means mechanism achieves lower error
The second and third random poset experiments break this data along dimensions (Figure 5). Fixing d = 10 (ignoring the root), we plot improvement as a function of both the depth (longest chain of relations) and number of relations the poset. Both numbers are computed on the transitive reduction of the directed acyclic graph corresponding to the poset, i.c., the directed acyclic graph that minimizes the number of edges while preserving all paths of the poset. As observed for d, at high level we find that larger and richer poset structures lead to correspondingly more dramatic improvements, up reduction in error.
0.32
0.31
0038t nomak. narm
poset peset narna. nom
0.295
0.290
0.28
0.285
0.280
0.27
0.275
0.210
0.25
10
20
22
24
26
28
30
Figure 5: Each point records the average mean squared & norm ratio between the poset and for balls over at least 100 trials. We omit extremes of both depth and number of edges, as they do oceur enough times in our overall sample of 5000 random posets to cross the 100-sample threshold.
4.4 NATIONAL HEALTH INTERVIEW SURVEY
The final set of experiments caid, 2024). As described in the introduction, the survey includes or omits certain questions depend- ing previous answers. This induces poset, and our experiments either the first, first two,
the National Health Interview Survey (NHIS) (Services & Medi-

---

Published as a conference paper at ICLR 2025
first three sections of the survey (Hypertension, Cholesterol, and Asthma). The resulting posets have size from = 4 to d = 15. As shown in Figure 6, our mechanism more roughly halves the error of the baseline mechanism.
# survey sections
poset ball squared l norm 1. ball squared & norm
0.573
2
0.503
3
0.460
Figure 6: NHIS average mean squared &g norm ratios, from 10,000 trials each.
4.5 RUNTIME
Empirically comparing our algorithm's speed to the general ((d+t)) sampler from Laddha et al. (2020) is hard, their algorithm is complex and relies asymptotic statements that make accurate implementation difficult to the best our knowledge, no public implementation of the algorithm exists. However, in addition its (dd² runtime, provide experiments demonstrating the empir- ical speed of our algorithm over random graphs of varying depth. In Figure 7 we plot the average runtime of sampling the poset ball the dimension d varies. On CPU machine with 32GB RAM, our method takes less than half a second for any of the d used in our experiments.
0.30
0.25
runtime
0.20
0.15
0.10
0.05
0.00
0
10
20
30
40
50
dimension d
Figure 7: Poset ball sampler average runtime to generate one sample. For each depth we average over different uniformly random posets and over samples of the mechanism.
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. 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 ge- ometric problem changes from sampling the induced norm ball to computing of expected squared & norm) ellipse enclosing the induced norm ball. Unfortunately. while Joseph & Yu (2024) solved this problem for count and vote, their solutions relied on the norm balls being symmetric around the vector (l,..., 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.
"smallest" (in terms
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Jordan Awan and Aleksandra Slavković. Structure and sensitivity in differential privacy: Comparing k-norm mechanisms. Journal of the American Statistical Association, 2021.
Borja Balle and Yu-Xiang Wang. Improving the gaussian mechanism for differential privacy: An- alytical calibration and optimal denoising. In International Conference on Machine Learning (ICML), 2018.
Thomas Chappell, Tobias Friedl, and Raman Sanyal. Two double poset polytopes. SIAM Journal on Discrete Mathematics, 2017.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference (TCC), 2006.
Alexander Edmonds, Aleksandar Nikolov, and Jonathan Ullman. The power of factorization mecha- nisms in local and central differential privacy. In Symposium on the Theory of Computing (STOC), 2020.
Moritz Hardt and Kunal Talwar.
On the geometry of differential privacy. In Symposium on the Theory of Computing (STOC), 2010.
Matthew Joseph and Alexander Yu. Some Constructions of Private, Efficient, and Optimal K-Norm and Elliptic Gaussian Noise. In Conference on Learning Theory (COLT), 2024.
Assimakis Kattis and Aleksandar Nikolov. Lower bounds for differential privacy from gaussian width. In Symposium Computational Geometry (SOCG), 2017.
Aditi Laddha, Yin Tat Lee, and Santosh Vempala. Strong seff-concordance and sampling. In Sym- posium on Theory of Computing (STOC), 2020.
Chao Li, Gerome Miklau, Michael Hay. Andrew McGregor, and Vibhor Rastogi. The matrix mech- anism: optimizing linear counting queries under differential privacy. The VLDB Journal, 2015.
Ryan McKenna, Gerome Miklau, Michael Hay, and Ashwin Machanavajhhala. Optimizing Error of
High- Bingh-Dimessioall Statistical Queries under Differential Privacy. The VLDB Journal, 2018
Guy Melançon, Isabelle Dutour, and Mireille Bousquet-Mélou. Random generation of directed acyclic graphs. Electronic Notes in Discrete Mathematics, 2001.
Aleksandar Nikolov. Private query release via the johnson- lindenstrauss transform. In Symposium on Discrete Algorithuss (SODA), 2023.
Aleksandar Nikolov and Haohua Tang. Gaussian Noise is Nearly Instance Optimal for Private Unbiased Mean Estimation. arXiv preprint wrXiv:2301.13850 2023.
Aleksandar Nikolov, Kunal Talwar, and Li Zhang. The geometry of differential privacy: the sparse and approximate cases. In Symposium on the Theory of Computing (STOC), 2013.
Center for Medicare Services and Medicaid. National health interview survey https: //www, cms gov http:///bbotttteeeeegggggoooaaaa http:////rrrrsuoeeeeeeeeeeeeeeee centeeeeeeeeee///eeeeeee 2024.
A SAMPLER PROOFS
Remark A.1. The exposition from Chappell et al. (2017) defines the double order polytope of double poset (P, (P.I+.I-) O(2P.) O(2P-), defines the double chain polytope as C(2P,) C(2P-) and for a pair of chains C (C++ C-) it defines F(C) = (F and FC(C) = (F 2F' (C_). Removing these factors of 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 IR that excludes the dimension that is added from the E operation. Consequently. the triangulation of lemma 3.11 still holds. The reason we remove the factors of 2 is because the sensitivity space we interested in is CH(O((P)) U -O(P")) which is equivalent to our definition of the double order polytope Oz(P* where r the global maximum of P.
11

---

Published as a conference paper at ICLR 2025
P' = PU Then -)--ii convex polytope in R lying in the hyperplane 21 1. Let
Claim A.2. Let P be (d -
=
(VP)U V(-P) (0) where the C comes from the fact that the vertices of the convex hull of a finite set is subset of that set. Since (PPPPPPP)) has antipodal symmetry, then E CH U UPP' implies U-P") which means that the line segment between J and -I contains small 1-dim
Proof. We have
-I E CH neighborhood B around the origin such that B C CH U- -P'), so the origin not a vertex of CH((P' U -P"), we have that V(CH U U-P')) c (-P))
Now, suppose that V E (P) is not a vertex of CH U -P').. 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(P') LU (VPP')) that equals v. None of vertices in the support of this combination can lie in V(-P') because then the 21 coordinate of the combination would be less than 1 whereas the first coordinate of is 1. So v must be a non- singleton convex combination of points in V(P), contradicting the fact that is a vertex of ((P). So ((P) C (VCH((''UP") and similarly ((-P) c CVCC U- U-P') -P').. But by the previous paragraph, V(CH(P'U-P")) ((P)) so
O
Lemma 3.13. There is bijection between the set of non-interfering pairs of chains C (C+, C-)
- r. of the double poset (P--r, 3) of size |C|= -C+| | = d + 1 and the set of extended
bipartitions of P r. Moreover, given an extended bipartition, its corresponding non con-interfering pair of chains can be computed in time O(d)).
Proof. Suppose we have a non-interfering pair of chains C = (C+, where |C| = d d 1. Write each chain of filters as C. = Jj 5 ... S Jíc. for E (++-)) Then min(J]+1] - min(J])) 2
for 1 S S |Col - Any element p (min( (J++1) - min(J?)) lies in Jg. If it also lies in Jg. then E min( means there exists p' E J with p' = but J S Ju then implies that p E min min(J[,1.. a contradiction. Thus (min(J
min( S (Ji+ Jr), ) and similarly for (minn(J{+)) - mi)n( S (J/+1 Jj)) Then JI+1 S Jq implies (min(J]+1 - min(J?)) n (min(J]+1 - min [j](( = 0.
any > i, we have
Let N₂ = - (min(J
min(J?)). -mnn())))))))) The above implics |Nol 2 |Col 1. Moreover, N4 n N_ = 0 since No c (
and (U min(J 0 C |-1 min(J
@ since C' is non -nntinttrferrn.. Thus
IN+ A-NNN- = |N+1+ +
|C| - d p r|.
But N4 LNNNN_ C - N UN-NN PP -rl This means that NN+ partition p
and (mi 1)- - min(J = 1 for
< i |Col - 1. It follows that min(Jf) = J = 0.
This leads us to the following extended bipartition. Let a; = min(J (( - min minn//ccinn --,)- for
for 1 S i |C_|- - 1. Since filters or a; is incomparable to each element of (a:+1, .... 11,+--1) 1-).. In either case, 01 3A ... Ia @C__ |-1 is a linear extension of N and similarly b 3B 3B 1-1 is a linear extension of N_, so ((N+, 3), (N_, 3), 3 <B) is an extended bipartition of p r.
1 S < |C+1 - and b, = min(J - min(
are upwards closed, either a; 3 a, for some aj E (G.+,,..,(__1111
Conversely, given an extended bipartition NN, ZA- 3A AN+ bi 3B 3B b₁n 1), define sets m 0, m 0. m min(U NN (+1-)) for 2 < i N+1 + 1 and m, min(u 1 bin (+)= for < i < |N_ + 1. Define J to be the filter with minimal elements mn for < i |N^1 + and let J = 0. Let C. = J ç Ç J JiN-111' Then (C+, C-) is a non-interfering pair with |C+1 + +|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.
remains to verify the runtime of computing the non con-interfering pair of chains we constructed above. Without loss of generality, we focus on Jt. Filter J 0 and J is the set elements with
12

---

Published as a conference paper at ICLR 2025
in row [N+] of matrix M, computed in time O(d). Now, suppose we have computed J and want to compute J4+1. By comparing rows N+1 +
and [N+1 + 2 - i of M, we can compute the set P; of parents of aIN, [+1 that are not parents of OIN, H+2 (we include aN,, |+ p.) in time (d). Note that p: J1+1 Jr Then J = J LJ p; where disjoint union. Thus each filter of J -... S |N+1+1 can be computed time (dd), taking time O overall.
B EXPERIMENT PROOFS
B. EXPECTED SQUARED NORM
We start with simple result about the expected squared & norm, EZ. Recall from Section 4.1 that (X) denotes the expected squared lg norm of uniform sample from X.
Lemma B.1. Then E3 YY) +
Proof. uniformly sample X + Y, we can uniformly sample x E X, y E Y and then return d y-
Samples x and y embed into disjoint coordinates of & so |a @ vll | + llll2.
Lemma 4.1. Let (X) denote the expected squared Eg norm of uniform sample from X, and let By denote the d-dimensional unit Ep ball. Then (B()) d gamma function, and (²( d/3. Let Tp,d / be the minimum radius for which T contains ((P)). By the above, (r,.a = E3 (B:)).
3d
). wwhere I' is the (())()))))
d-2
Proof. We use the fact that So 10-2(1-1)0-1 -1)--2 [() T(a+b)
Then
E3(D))
Σ
x 0x Dad
2
1=1
| -1
de d 1ex Ixe
-B -1
/popptt..ttep/s1-11000 ax2..0xg
|B/| -1 ["] do? Bd-1 1111 - 111 - Oc
110 f x² xp) +ي Ox.
B
We substitute x² to get
Oy = pxp-1 Fx
dz prp-1 Dy
0r
y -1-10y Dg
13

---

Published as a conference paper at ICLR 2025
and the chain of equalities continues with p
(3 =
2
/
yē (1
v) -
3
y by
1
p
=
d d
3
L.
ya
3
(1 y) d-1
2 0y
3
p
2 I( ( +11
2
d
188-111
(g)
(3]
12 +1) r( T(
2 3
(2 + 1))
r( +1)
T p
+ () +1)
d
p
I( 1)
(2n + 1))a
d+2 +1)
2 3
r(g p +1)
p 11)
d
2 + +1)
1 1)
r r 2
3d
d+2
r())) d+2
For 00, use
d af." Pd d
=
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.I.
We show that Tpdd = d/P,, Note that Tp.d is equal to the smallest radius such that rp.a contains the point (1,..., 1) E (PP)) because if (1,..., 1) E By then all other binary vectors of length d are also contained in Pp. p. i.e. ('(P*) C Tg.
Next, we show that (Tp r2 (3 Since Tpa = (Tp.z : x E BB),
E3 aB) /B -1
Σ ()) 20 1 ...
Ixs tr.p+t..t i=1
B -1
x 0x ... .xd
|
= 3B
B.2 ANALYTICAL GAUSSIAN MECHANISM COMPARISON
14

---

Published as a conference paper at ICLR 2025
error comparison
gaussian
30000
20000
10000
40
Figure 8: A comparison expected squared Ea norms for the 1-DP &oo mechanism (with foo sensi- tivity 1) and (1, 10 10- analytical Gaussian mechanism (with & sensitivity vd).
15


Reviews:
[{"review_id": "JCoknArg8P", "reviewer": "Reviewer_dNFD", "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.", "questions": "How can the algorithm be adapted to approximate DP and achieve better results than pure DP?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Summing over items with partial orders is a fundamental problem that has not been fully studied under differential privacy. \n2. The proposed algorithm is very time-efficient, only quadratic in the number of bits. The speed-up is significant over some simple sampling algorithms\n3. 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.\n2. 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.", "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": "", "extra_scores": {}}, {"review_id": "gcaX0FHeCH", "reviewer": "Reviewer_a51u", "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.", "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.\n\nAlso, 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?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 1, "contribution": 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)$.", "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. \n\nIf 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.", "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": "", "extra_scores": {}}, {"review_id": "uahTXQbxEP", "reviewer": "Reviewer_jiCC", "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.\n\nThe 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.\n\nThe 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.\n\nThe 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.", "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.\n- 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.\n- 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.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "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.", "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": "", "extra_scores": {}}, {"review_id": "6SVWW05BfU", "reviewer": "Reviewer_dkVy", "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.", "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.\n\nIt 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.\n\n\nQ2: 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.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "S1: This paper addresses the problem by providing a sampler with more than cubic speedup over the previous algorithms. \n\nS2: The proof path leading to the final sampler is clear and well-organized.\n\nS2: This paper also investigates the rejection sampling and provides a negative result. \n\nS3: 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)\n\nW3: The results of the experiments appear to be incomplete (also summarized in questions.)", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)