Faster Differentially Private Top-$k$ Selection: A Joint Exponential Mechanism with Pruning
Authors: Hao WU
Hanwen Zhang
Venue: NeurIPS 2024 poster (2024)
Keywords: Differential Privacy
Top-k Selection
Exponential Mechanism
Primary area: privacy
TL;DR: A fast differentially private joint exponential mechanism for top-$k$ selection.

Abstract: We study the differentially private top-$k$ selection problem, aiming to identify a sequence of $k$ items with approximately the highest scores from $d$ items. Recent work by Gillenwater et al. (2022) employs a direct sampling approach from the vast collection of $O(d^k)$ possible length-$k$ sequences, showing superior empirical accuracy compared to previous pure or approximate differentially private methods. Their algorithm has a time and space complexity of $\tilde{O}(dk)$. 

In this paper, we present an improved algorithm that achieves time and space complexity of $\tilde{O}(d + k^2)$.
Experimental results show that our algorithm runs orders of magnitude faster than their approach, while achieving similar empirical accuracy.

Faster Differentially Private Top-k Selection:
A Joint Exponential Mechanism with Pruning
Hao WU University of Waterloo Canada
Hanwen Zhang University of Copenhagen Denmark hazh@di ku.dk
hao h @wwaterlo..cc
Abstract
We study the diffcrentially private top-k selection problem, aiming to identify a sequence of k items with approximately the highest scores from d items. Recent work by Gillenwater et al.) (ICML '22) employs direct sampling approach from the vast collection of d (())) possible length- k sequences, showing superior empirical accuracy compared to previous pure or approximate differentially private methods. Their algorithm has a time and space complexity of (dk).
this paper. we present an improved algorithm with time and space complexity (dd+k2/E /s-In In df where denotes the privacy parameter. Experimental results show that our algorithm runs orders of magnitude faster than their approach, while achieving similar empirical accuracy.
Introduction
Top-k selection is fundamental operation with wide range of upplications: search engines, commerce recommendations, data analysis, social media feeds etc. Here, we consider the setting where the dataset consists of d items evaluated by people. Each person can cast at most vote for each item, and vote for unlimited number of items. Our goal is to find a sequence of items which receives the highest number of votes.
Given that data can contain sensitive personal information such as medical conditions, browsing history, or purchase records, we focus top-k algorithms that are differentially private (Dwork et al. 2006): it guaranteed that adding/removing an arbitrary single person to/from the dataset does not substantially affect the output. Research for algorithms under this model centers around how accurate the algorithms can and how efficient they are.
Significant progress has been made in understanding the theoretical boundaries. There are approx- imate differentially private algorithms (Durfee and Rogers 2019 Qiao et al., 2021) that achieve asymptotic accuracy lower bound (Baina and Ullman, 2017 Steinke and Ullman 2017), and have
((d) time and space usage.
There is also a research endeavor aimed at enhancing the empirical performance of the algorithms. particularly noteworthy one is the JOINT mechanism by Gillenwater, Joseph, Medina, and Diaz (002)). which exhibits best empirical accuracy across various parameter settings. Diverging from the prevalent peeling strategy for top-k selection-wherein items are iteratively selected, removed and repeated & times-the JOINT mechanism considers the sequence holistically, directly selecting an output from the space comprising all d (Kk) possible length-k sequences.
While the algorithm has running time and space Öddk), successfully avoiding an exponential time or space consumption, it notably incurs a higher computational cost than its ( counterparts. This prompts the interesting question:
"This work conducted while the author was Postdoctoral Fellow at the University of Copenhagen. A simplified bound from Thcorem 4.1 for a wide range of failure probabilitics concerning solution quality.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Research Question: Can we design a mechanism equivalent to the JOINT mechanism with running time and space linear in d?
Our Contributions.
Our paper answers the research question when k is not too large. Specifically, We present an improved algorithm with time and space complexity of O(d + k2/e- In
This is an informal statement of Theorem 4.1 When k E O(vd) (a common scenario in practical settings), the time and space complexity simplifies to (dd). Moreover, the proposed algorithm achieves the same asymptotic accuracy guarantee as the JOINT mechanism.
Similar to the JOINT mechanism, our algorithm is an instance of the exponential mechanism (detailed in Section 3) that directly samples from the output space comprising all length-k sequences. We introduce a "group by" sampling framework, which partitions the sequences in the output space into O(nk) subsets, aiming to streamline the sampling process. The framework consists of two steps: sampling a subset and then sampling a sequence from that subset. We provide efficient algorithms for both steps. Furthermore, uniformly. This technique effecttiveyy reduces the number of subsets to Ó(k?), leading an algorithm in O(d + k²) time and space complexity.
introduce a pruning technique to handle outputs with low accuracy
Finally, we perform extensive experiments to
Verify the theoretical analysis of our algorithm.
Demonstrate that algorithm runs 10-100 times faster than JOINT the tested datasets.
Show that our algorithm maintains comparable accuracy to JOINT.
Organization. Our paper is structured as follows: Section into the necessary preliminaries for our algorithm. Section J introduces novel algorithm, and Section presents our experiment results.
Section 2 formally introduces the problem, while
2 Problem Description
Let = (1....,d) d} be a set d items and 2f = {1...., n) be a set of n clients. Each client v E 2/ can cast most one vote for each item, and can vote for unlimited number of items. For each item i D, its score fi]i] is the number of votes it received. The histogram is vector h = (K[1),... ... h(d)
[0. [0..n]]. Define PD. = ((i ix) D :i,,..ig in are distinet) be the collection of all possible length-k sequences.
The differentially private top-k selection problem aims at finding a sequence from PD. with approxi- mately largest scores, while protecting the privacy of each individual vote.
Privacy Guarantee, Two voting histograms h, h' N' are neighboring, denoted by h ~ Ri, if H can be obtained from h by adding or removing an arbitrary individual's votes. Therefore, when h ~ R', we have || - | < 1, and h < H' or h Z R'. To protect personal privacy, a top-k selection algorithm should have similar output distributions neighboring inputs.
Definition 2.1 ((E, 8)-Private Algorithm (Dwork and Roth 2014)). Given E, > O, randomized algorithm M No > PD, is called (c, diffferrrnnll private (DP), for every h, W. E (dd such that h N., and all Z PP.
Pr[M(N) S 2 +
Pr(M(T))
An algorithm M is also called c-DP for short, if it is (c, DD. If an algorithm is e-DP, it is also called pure DP, whereas called approximate DP if (c, 6)-P. Although we present the definition in the context of top-k selection algorithms, it applies more generally to any randomized algorithms M X + V, where is the input space, which associated with symmetric relation that defines neighboring inputs.
Remark:

---

3 Preliminaries
3.1 Exponential Mechanism
The exponential mechanism (cChhery and Talwar 2007 is a well-known differentially private algorithm for publishing discrete values. Given general input space X' (associated with a relation which defines neighboring datasets), a finite output space } the exponential mechanism Mexr a randomized algorithm given by
X
Pr [Mxxp (a) y| exp (-s- Exx v) (2. AEX))), Ve E X, y E EV,
(2)
where ExxP= X x y + IR is called the loss function measuring how "bad" y is when the input is æ. and Axx is the sensitivity of Exxp which is the maximum deviation of EpxP:
A
max
(xxp(x, y) Exxo ,))
Bowar DEY
Fact 3.1 (Privacy (McSherry and Talwar 2007)) The exponential mechanism MEX E-DP.
Fact 3.2 (Utility Guarantee (McSherry and Talwar 2007)). For each 3 E (0,1), and = 2.A
| In B. the exponential mechanism Mexe satisfies
Pr [Exxe (Z, MExe (z)) 2 minyey Exxp(x, v) + + B, Vr X.
Implementation. Given imput x E X, a technique for implementing the exponential mechanism is to add i.i.d. Gumbel noises the terms of {-s (xx y) (2 DxxP) E), and then select the y corresponding to the noisy maximum.
Definition 3.3. Given b > O, the Gumbel distribution with parameter b, denoted by Gumbel (b), has probability density function p(z) = eex (-(# exp (-)))), Vo E
Fact 3.4 (Yelloo 1977 Assume that wi; 2 for i E [m], and X; ~ Gumbel (1), [m]] are independent random variables. Then Pr = arg max]e[[] (X, + w;)] x wi-
follows that, if Xg ~ Gumbel (1) E y are independent random variables, then Pr yy = arg max (X, -E Exxe (x. v/) / (2 Axxe] x exp (-E Exxe(x,)) v) (2 AEX)))
3.2
JOINT Mechanism
The JOINT mechanism MIONT Na + Pa. Gillenwater et al. 2022 is an instance of the exponential mechanism which samples a sequence [B]1]...... (Tk] directly from PD, with the loss function
EJoNr (h, 8) = maxie[s] (ho) - [[st]]),
where Tigy is the true (th) largest entry in h. can be seen that E-oINT()) has sensitivity A
Observe that a naive implementation of this exponential mechanism needs evaluating and storing the scores of [Po. = d (()) sequences. Remarkably, Gillenwater, Joseph, Medina, and Diaz 2022 demonstrate that the exponential time and space requirements can reduced to polynomial.
Fact 3.5 (JOINT Mechanism (Gillenwater et al.) (022)). There is an implementation of exponential mechanism which directly sample sequence from PD, according loss function EsoNNT (h, 3) max4e[k] (Tie) - ] with time (dk log k + d log d) time and space (dk)).
For completeness, we includes short proof of Fact 3.5 in Appendix A Let 3" corresponds to the k items with the largest scores. Then clearly min; EjANt (h EJONT (h, 5*) 0. Combining [Po,al = ( k! and ATONT 1, and applying Fact 3.2 provide the theoretic utility guarantee of JOINT.
Fact 3.6 (Utility Guarantee). For each 3 E (0, 1). T In (f) #
E @
(kl In })),
Pr[EsoINT MJOONT(h) (7))
(5)
3

---

4 Algorithm
In this section, we present an algorithm which has similar output distribution as the JOINT mecha- nism (Gillenwater et al. 2022). but reduces the time and space complexity to O(d k- T). The main result stated as follows.
Theorem 4.1. Let B E (0, 1), = .. ( and A No PD, be the top-k algorithm
Pr [A(h) = 5 oc exp (-E Ea 8) (2-
where EA 3) min (EJONNT (),3), T), and A is the sensitivity of &.A. Then A e-DP and has an implementation with time and space complexity O(d + k -T). It satisfies the following condition:
Pr(EsonnT(h,.4 A(h)) 2 7| S.
Simplification. When 1/3 E (dd)), the error reduces to Old + /e-/ndd).
can be verified that the sensitivity AA 1. Since A is also an instance of the exponential mechanism, its privacy guarantee naturally follows from this property. As for the utility guarantee, instead of expressing it in terms εA (and directly applying Fact F.2) we express it in terms of the loss function EJONT- The error achieved mirrors that of JOINT, as stated in Corollary 3.6
Road map. In Section 4.1 we first propose novel "group by" framework for sampling a sequence from the space of all possible length-k sequences. Then, we introduce a new choice of groups to materialize this framework, leading to a new algorithm with O nk) time complexity. In we propose a new pruning technique that reduces the running time to O(d rk).
Section 4.2
A detailed comparison with JOINT is deferred to Section b where we will explain JOINT in the context of the novel framework and compare it with our new algorithm.
To simplify notation, when the input histogram clear from the context, we use {5) as shorthand for Esonnt (h, 3), and (8) shorthand for E (h 8).
4.1 Sampling Framework
Partitioning. We begin with novel framework for designing algorithms that produces the same output distribution as JOINT. Let Pi,..., Pm be an arbitrary partition of PD, It is called &- consistent, if all sequence belonging the same subset have the same loss (w.r.t loss function E): Vi E [m], V5, 5" E P., E(}) = E(3"). ). We regard EPP) as the loss of the sequences in P.. Given this partition, we can design an algorithm that reproduces the output distribution of JOINT using two-step approach:
Subset Sampling: sample a subset P; with probability proportional to [P]] e (-e ( E(P.)22).
Sequence Sampling: sample an P; uniformly.
There can be more than one choices of partitions of Po, We would like find one which enables efficient sampling algorithms for both steps. We first consider the partition Sy, E n0..n], [R:]. given by:
[
Tus r, Vj <
S i 3= (3T1), ..... Jb) PD.:: E(3) = and h
s
h() - r, j=i- hG) - Vj>
(8)
7 [
Based on the definition to and denotes the index of the first coordinate reaching this loss. Hence, E(S,;) = Via Fact to sample an S, with probability proportional to |S,.a -lpppeepp ( (-E ---rr/2, r/2), we can compute the maximum of { (Xr.s + In (SS..l exp (-s -r/)) (r, i) E [o..n] x [k]]. where X,, ~ Gumbel (1).
Equation 4 Sr,, represents the subset sequences with an loss equal
The first key advantage of the partition being discussed is that, each In [St.al can be expressed sum of l terms and it can be computed efficiently.
Definition 4.2. For each E [0.. j [k), define Oru = Ki E [d] hD's 2 hgz r3/-

---

Lemma 4.3. For each r E m0. E [kd) it holds that
In 115al=E; (C - (j 1)) + In (Cr, - Cr-13) + Ejein Ia (Crs - (j ()).
Lemma 4.4. For all E [ E [k). Cru can be computed in Old + nk) time. Furthermore, given the Orj for all r E [0..m]] n). in Sr, can be computed in (nk) time.
The algorithms for proving Lemma 4.4 are detailed in Appendix At a high level, for a fixed r, the Crg-j E [k] constitute monotone sequence, enabling us to devise recursion formula to compute them. Additionally, the prefix sums (the first term) and the suffix sums (the last term) Equation (9) can be pre-computed, simplifying the computation of In |S, to adding only three terms.
Here, we present proof for Lemma 4.3 offering insights into the structure of S,,i.
Proof for Lemma 4.3 It sufficess to show that
|S.a]
(C,-15 - 1)- ():: -G-11 I (Cr,s (j 1)).
(10)
The proof is via standard counting argument: assume we want to select sequence 3 E S, Since $11] (5' [d] MD'l he)) r). the number of possible choices for s{1] is
He [d] Rbl Ro) r)1 Hi [d] MD") 2 h(1) - (r 1)H1 Cr-1,1
The first equality holds because the M[j'] values integers.
Next, since kn) 2 h(zy. it also holds that s[1] {J' E [d] Roo h(2) -r). After determining
$11) the number of choices for s[2] is It E [4] M['') > hie - r]] - 1 = C, - 1. Continuing this argument, for each j E [1..1 1], the number of choices for $1ʃ), after determining $(1.. 1], is Hi' E [d] MD' h)y - r]] - (j
Cr-1s (j- -).
Now we consider the number of choices for sti]. Since $11), ... B 1] E (i E [4] A[jl]
h(a) - rJ. they do not appear in { E [d] M[j'] = hua - r}. The number of choices for s is exactly 1[3 [d] M[j' h r) C,, C,-
The cases for j E [i + 11... are similar to the cases of j E [1 1]. Since hun 2 h(2) 2 hig-)). it holds that $[1], ................................ $ - 1] fJ' [d] Mil'l 2 hg) r). As result, for 1.. K.) the number of choices for $[. after determining $[... 1]. is Cr,
1).
Multiplying the number of choices for each element in E Sr we obtain Equation
TTP.
The second key advantage of the partition being considered is that, there is an algorithm for sampling uniform random sequence from S, in ((d) time, as implicitly suggested by the proof for Lemma 4.3
Further details of this implementation are provided in Appendix B
4.2 Pruning
The previous discussion suggests an new algorithm with Old + nk) running time. Based on Lemma 4.4 computing the Cr, values for r E [0. n2] and [k] takes O(d + nk) time. The total time to compute In [S,&i I for r [O.. n] and i E [k] is O(nk). Finally, sampling a sequence from the chosen S takes (dl) time. The bottleneck here lies in the nk term, which arises from the need to compute the Cryys 's and In S,,,l's 's for all r E [0...n].
However, this is unnecessary. We need only to consider the cases for r E [0..r]. The key observation that, the probability of sampling an 5 PD, decreases exponentially with increasing (()).
Claim 4.5 (Restatement of Fact 3.6). The probability of sampling an 5 with E(5) 2 T at most B.
To provide further insight, we present short proof here. Let S2- = (5 PD. {()) 2 T), then
Exerg, --
Pr [sampling an E' S2r S
-18 S SPD.A -- =8, (11)
5

---

where 5" is the k items with the largest scores and E(5*) 0.
Given this, if we slightly adjust the loss function of sequences in S2r, their probabilities of being outputted will not be significantly affected. It motivates to consider the truncated loss function: (5) = min (E)),, 7), and an algorithm A which samples & with probability proportional to 11 still holds if we the E() with Ea(:), we immediately obtain the
-- As inequality following lemma.
Lemma 4.6. The probability of A sampling an 3 with {5) 2 T is at most B.
Subset Merging. The most important benefit of truncated loss is that, it allows us to reduce to the number of subsets in the partition Sy r E n.,. i E [k] from O(nk) to O(Tk). In particular, for each i E [k], as the sequences in the subsets S, E [T..n] has the same truncated loss, it suffices to merge them into one
2n Urelr .n Se. 8- 8 ... (1)) E PD,
A [ hU T, Vj マ j=i
(12)
h s
S hτ5)
Szn, shares a similar formula on its size as Equation ( and can be uniformly sampled efficiently. Lemma 4.7. For each i [k)]. we have
In ||+,2 Ej= In (C+-1,j - (j - 1)) + In (d - C.-1.) + Ej=utz In (d- 1)).
(13)
Lemma 4.8. Given the C+-1.5 's, each In |2r,a can be computed in (1) amortized time.
The proof for Lemma 4.7 is provided in Appendix A while an algorithmic proof for Lemma 4.8 can
be found in Appendix
Experiment
In this section, we compare our algorithm, referred to FASTJOINT, with existing state-of-the-art methods on real-world datasets. Our Python implementation is available publicly
Datasets. We utilize six publicly available datasets: Games (Steam video games with purchase counts) (Tamber) 2016). Books (Goodreads books with review counts) (Soumik 2019). News (Mash- able articles with share counts) (Fermandes et al. 2015), Tweets (Tweets with like counts) (Bin Tareaf 2017), Movies (Movies with rating counts) (Harper and Konstan 2016 and Foods (Amazon grocery and gourmet foods with review counts) (McAuley et al.] 2015). Table summarizes their sizes.
Dataset
Games
Books
News 39,644
Tweets
Movies 59,047
Food
#items
5,155
11,126
52,542
166,049
Table 1: Dataset Size Summary
Apart from the JOINT mechanism (Gillenwater et al. 2022). we consider the following two candidates: the peeling variant of permute-and-lie flip mechanism (McKenna and Sheldon 2020). denoted PNF-PEEL; and the peeling exponential mechanism (Durfce and Rogers 2019), denoted CDP-PEEL. We don't 't compare with other mechanisms, e.g. the Gamma mechanism (teiikke and
Baselines.
Ullman 2016) and the Laplace mechanism (Bhaskar et al., 2010; Qiao et al. 2021 which are
empirically dominated by PNE- and CDP- respectively (Gillenwater et al. (022).
PNF-PEEL: The permute-and-flij is an e-DP mechanism for top-1 selection. It can be implemented cquivalently by adding exponential noise (with privacy budget e/k) to each entry of and reporting the item with the highest noisy value (Ding et al., 2021). To report ls items, strategy: select one item using the mechanism, remove it from the dataset, and repeat this process times, resulting in running time of (dk).
the peeling
CDP-PEEL: The (e, -DP peeling exponential mechanism samples items without replacement, selecting one item at a time using a privacy budget of Ö(s Vk) according to the exponential mechanism (McSherry and Talwar 2007). Duufee and Rogers 2019) demonstrate that CDP-PEEL has an equivalent (dd)timm implementation.
The code for all competing algorithms was obtained from publicly accessible GitHub repository by
Google "esearct"" written Python.
hicrpp://gtthuub..com//bb
wtwpiittuu.coo///iea cww.suhao wttp:///wwuaaoooaaannaaaaaiaiaie

---

Experiment Setups. The experiments are conducted on macOS system with M2 CPU and 24GB memory. We compare the algorithms in terms of running time and error for different values of k. E and 3. Note that the parameter /3 (see Theorem (41) only affects our algorithm. The (e, 6)-DP mechanism CDDP-PERL is configured with a parameter of 10-6, consistent with prior research (Gillenwater et al. 2022).
Error Metrics. We evaluate the quality of solution 5 ususng both 6so and & errors. The Lo error is defined as max [/(()- - =[i],, while the & error given by Σie(a] [1(g)) - -|i]].
Parameter Ranges. The parameter ranges tested are as follows:
k= = 10,
200, E == 1,,,1,
B --2-0,2-8,2 2-.2222112222 2-,2-
The values indicated by underlining represent the default settings. During experiments where one parameter is varied, the other two parameters are kept at their default values.
5.1 Results
All experiments are repeated 200 times. Each figure displays the median running time or lo or & error as the center line, with the shaded region spanning the 25th to the 75th percentiles.
Varying A: Figure presents the results for different values k. FASTJOINT consistently outperforms JOINT in terms of execution speed, running 10 100 times faster across various datasets. FASTJOINT is slower than CDP-PEEL; the later has theoretical time complexity (dd) and therefore this is expected.
We observe "jumps" in running time of JOINT on the games and food datasets. This phenomenon can also be found in the original work by Gillenwater al. (2022) in the only running time plot for the food dataset. Upon investigation, we found that, as noted in their code comments, the current Python implementation of the Sequence Sampling step of JOINT has worst-case time complexity of O(dk²) instead of (dk:). Although this step does not constitute a bottleneck in their code and accounts for a constant fraction of the total running time, it still introduces instability in the running time. To delve deeper into this issue, we provide a comparison in the appendix where we plot the running time of JOINT (excluding the Sequence Sampling step) against the running time of FASTJOINT (including the Sequence Sampling step), resulting in smoother time plots. Even with this adjustment, JOINT remains order of magnitude slower.
Interestingly, for small datasets, FASTJOINT can be slower than complexity. This is because PNF-PEEL has simple algorithmic structure that can be implemented as & rounds of vector operations: each round involves adding a noisy vector to the input histogram and then selecting an item (not previously selected) with the highest score. It is well-know that vectorized implementation 5 ggain significant speed boosts by utilizing dedicated Python numerical libraries such as NumPy (Harris et al.) 2020). However, as the dataset size increases (e.g., the food dataset), FASTJOINT outperforms PNE-PEEL in terms of speed.
which has an (dk) time
In terms of solution quality, even with the pruning strategy, FASTJOINT does not experience quality degradation compared to JOINT. delivers similar performance to JOINT across all datasets and performs particularly well the books, news, tweets, and movies datasets, where there are large gaps between the top-k scores. (Due to space limitations, the complete plots of these score gaps included in the appendix. with partial plots provided in Figure 2p. FASTJOINT consistently outperforms the pure diffcrentially private PNF-PEEL for all values of & and the approximate differentially private CDP- for least moderately large k. These results align with the findings of Gillenwater et al. 2022), who compared JOINT with PNE-PEEL and CDEL
Varying 8. Due to space constraints, Figure 2 presents results for different values of on two typical datasets: one where FASTJOINT performs well and one where it does not. We replaced the & error plot (as it exhibits similar trends the Exo plots) with a plot showing the gap between the top-300 scores]] The complete plots across all datasets are included in Appendix C The running time comparison resembles that of the varying-k plots in Figure with one notable difference: the running time of FASTJOINT exhibits clear decrease as increases. This observation aligns with our theoretical statement about the running time of FASTJOINT, as detailed in Theorem 4.1
'In Appendix B we discuss more detail the possibility of implementing FASTJOINT with vertoziation.
'The & used for the varying experiments is 100; here we plot the gap for the top-300 scores
7

---

10a
10
10
10-1
time (5)
1. erroor
102
F: erroor
-0a
10"2
102
10
10-3
10a
100
200
100
150
200
50
100
150
200
books
books
books
10a
10a
10
102
time (9)
error
error
102
10-2
10
101
10a
9-0-0-6-0
109
0-0-0-6-
150
200
100
150
200
50
100
150
200
10a
10a
10a
10a
107
time (5)
10
1. errorr
4: error
10a
10
101
10-3
10a
8-8-0-0-6
109
0-0-6-0-6
100
150
200
100
150
200
50
100
150
200
10a
10a
109
10a
102
time (5)
2. eerror
4: error
102
10-2
0.0000000
10a
10a
8-0-0-6-6-
6- 6-66--
10a
100
150
200
100
150
200
50
100
150
200
movies
mavies
10a
104
10a
time (5)
2- eerror
f1 error
10-1
102
10a
10-2
101
10a
0-0
-00-0-0-000
10a
100
150
200
50
100
150
200
50
100
150
200
food
10a
10a
10a
10c
time (5)
error
107
41 errror
10a
1102
10-1
10a
101
10-2
10a
10a
50
100
150
200
100
150
200
50
100
150
200
k
Fastjoint
Joint
......
CDP Peel
PNF Peel
Figure 1: Left: Running time k.
Center: for vs kt
Right: E vs At.
The fi plots are padded by to avoid log 0 on the y-axis.

---

games
games
10a
10'
10a
diff
time (5)
I. error
10a
10
10?
10
102
100
300
news
news
10
103
10a
10*
diff
time (5)
1. error
102
10a
10-2
10
10
109
10a
1
2
2
100
260
300
..... Fastjoint
Joint
CDP Peel
.....
PNF Peel
Figure 2: Left: Running time E. s.
Center: too error vs E.
Right: Top-300 scores gaps.
The f plots are padded by 1 avoid log 0 the y-axis.
In terms of solution quality, FASTJOINT and JOINT perform particularly well on the news dataset and only slightly better than PNF-PEEL and inferior CDP-PEEL on the games dataset, where the gaps between the large scores in the former dataset are significantly larger than in the latter (note the values on the log-scale y-axis). We provide informal but informative explanation for this phenomenon: based on Lemma 4.6 FASTJOINT is unlikely to sample sequences with loss greater than r. Furthermore, when the distribution of top-k score gaps is highly skewed, there are very few sequences with errors between (0, r], and the likelihood of sampling these sequences scales with O()) as varies. In contrast, the gpeling-basee mechanism needs to divide its privacy budget by k or Ö(V)) for each round, causing the sampling probability of an error item to scale only with O(=/k) or -Ote/Vk), which higher than e ((e).
Varying 3. Due to space constraints, Figure 3 presents results only for different values of /3 on a medium-sized dataset. Similar plots for other datasets can be found in Appendix is anticipated that JOINT, PNF- and CDP-PEEL do not exhibit significant performance variation concerning 3. However, it is somewhat surprising that FASTJOINT does not neither. This stability can be attributed the threshold used for pruning, given by ? In (()) k./B)]. The numerator inside logarithm term, (c) k!, grows as (K)), significantly overshadowing 1/3. Consequently, changes only slightly 3 varies. This experiment demonstrates the robustness of FASTJOINT's pruning strategy concerning the choice of B.
tweets
tweets
tweets
1200
300
1000
250
800
10-1
400
10
200
10
10
10
10 -4
10
10
10
10
10
Figure 3: Left: Running time vs B.
Center: Eo enror vs B. Right: & error vs B.
The f plots are padded by 1 avoid log 0 on the y-axis.

---

Related Work
Comparison with JOINT. We can also explain JOINT (Gillenwater al. 2022) within the novel framework proposed in Section[4.1 which consists of the Subset Sampling and Sequence Sampling steps. Their approach assumes that [[1] 2 ... 2 [d]] which can be achieved by sorting h. For each i E [K] and [d]. define Et, = h(j] h[j]. The partition they consider is equivalent the one defined as follows:
{ 8= ($1)....
7 [ > M(q
Eijs
Ve <i) t=i <i>i)
U3 =
, sT()) =
PD. :
8 J.
, e [M] [d].
A [
2 M0 Eijr
Intuitively, Us. consists of the length-k sequences, 5, that satisfy: 1) the 7th element in 5 is exactly element j: 2) the first 1 elements in have losses less than Exg; and 3) the last k elements in s have losses at most Er.j-
Therefore, the sequences i' Ut, share the same loss, (J, 3) = E,, (as defined in Equation with the first position reaching this loss being the 8th position, where element j appears. Further- more, sequences in different subsets, U1_ and Up can share the same loss, as it is possible that E = E There are dk subsets in this partition, resulting in a running time of (dlk) for their implementation (Gillenwater et al. 2022).
Applying the pruning technique this partition can not reduce the number of subsets to o(dk). Let be as defined in Theorem 4.1 For each i E [k), we aim to find the first j such that A[j] - h(3 т. Denote this value by (i) = min [d] M[j] s hug -) Following the spirit of our pruning technique, we would like to merge the trailing subsets Uz,r(t): ... Ui, into single subset Uz))(1) = U) ULJ to reduce the number of subsets. However, it is easy to find counterexamples where (dd) items are equal to h(s for all i E [k]. For example, consider the case where h[1] A(2) hid]- = c, for some constant c. In such scenarios, we still have (ii) E 22(),, and therefore, in the worst case, the number of subsets remains ΣiE(K] (i) (ddk)).
The technique of applying the exponential mechanism with truncated scores was considered by Bhaskar et al. (2010). Their top-k selection algorithm employs a peeling- approach: it samples k items without replacement, selecting one item at time using the exponential mechanism with truncated scores. This method is employed because, in their setting, obtaining the scores of the input histogram / is expensive, leading them to treat lower-scoring items uniformly by assigning them a small, identical score. In contrast, when all scores of i are known, iteratively applying the exponential mechanism to select the top-k items has an equivalent linear time imple- mentation (Durfee and Rogers 2019) (the CDP-PEEL algorithm in Section 5). Therefore, truncating the scores of h is unnecessary in this case.
Truncated Loss.
Adaptive Private & Selection. As the experiments show, the performance of JOINT and FASTJOINT depends on gap thee-hhey perform well when there are large gaps between the top-k items. An orthogonal line of research (Zhu and Wang. 2022) leverages large gaps to privately identify the index i that approximately maximizes the gap between the 7th and (i + 1)th largest elements. This followed by testing whether the gap (using techniques like propose-test-release) between the 7th and (i + 1 largest elements is sufficiently large, allowing the top-i items to be returned without additional noise. This approach benefits by adding no noise the final step. However, there are two key differences: 1) it does not guarantee returning at least k items, as i can be less than k; 2) more crucially, the top- items must be returned as an unordered set. The first issue can be addressed by iteratively applying the above mechanism. For the second issue, algorithms introduced in this paper, such as CDP-PEEL and FASTJOINT, can serve as subroutines. Notably, FASTJOINE may provide better empirical performance when large gaps exist among the top i items.
Utility Lower Bound. Bafna and Ullman| 2017) and Steinke and Ullman (0177 demonstrate that, for approximate private algorithms, existing methods (Durfee and Rogers 2019 Qiao et al. (021). ) including CDP-PERI. (Durfee and Rogers) 2019) as compared in Section achieve theoretically asymptotically optimal privacy-utility trade-offs.
10

---

Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for their feedback which helped improve the paper. Hao WU was Postdoctoral Fellow at the University of Copenhagen, supported by Providentia, Data Science Distinguished Investigator grant from Novo Nordisk Fonden, and affiliated with Basic Algorithms Research Copenhagen (BARC), supported by the VILLUM Foundation grant 16582. Hanwen Zhang affiliated with Basic Algorithms Research Copenhagen (BARC), supported by the VILLUM Foundation grant 16582. Hanwen Zhang is partially supported by Starting Grant 1054-00032B from the Independent Research Fund Denmark under the Sapere Aude research career programme.
References
M. Bafna and J. R. Ullman, "The price of selection in differential privacy," in Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017, ser. Proceedings of Machine Learning Research, S. Kale and O. Shamir, Eds., vol. 65. PMLR, 2017, pp. 151-168.
R. Bhaskar, S. Laxman, A. Smith, and A. Thakurta, "Discovering frequent patterns in sensitive data," in Proceedings of the 16th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, ser. KDD '10. New York, NY, USA: Association for Computing Machinery, 2010, p. 503-512.
R. Bin Tareaf, "Tweets Dataset Top 20 most followed users in Twitter social platform," " https wtt.:org/10.9910/DYO ) 2017, Accessed: 2024-05-10.
Ding, Kifer, S. M. S. E., Steinke, Y. Wang, Y. Xiao, and D. Zhang, "The permute-and-flip mechanism is identical to report-noisy-max with exponential noise," CoRR, vol. abs/2105.07260, 2021.
D. Durfee and R. M. Rogers, "Practical differentially private top-k selection with pay-what-you-get composition," " in Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, M. Wallach, H. Larochelle, A. Beygelzimer, d' Alchhh Buc, E. B. Fox, and R. Garnett, Eds., 2019, pp. 3527-3537.
C. Dwork and A. Roth, "The algorithmic foundations of differential privacy," Found. Trends Theor. Comput. Sci., vol. 9, no. 3-4, pp. 21 1-70 2014.
C. Dwork, F. McSherry, K. Nissim, and A. D. Smith, "Calibrating noise sensitivity in private data analysis," " in Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings, ser. Lecture Notes in Computer Science, S. Halevi and T. Rabin, Eds., vol. 3876. Springer, 2006, pp. 265-284.
K. Fernandes, P. Vinagre, and P. Cortez, "Online News Popularity," UCI Machine Learning Repository, http://dbo..rr/1102444333 1124434///33333333 2015, Accessed: 2024-05-10.
J. Gillenwater, M. Joseph, A. M. Medina, and M. R. Diaz, "A joint exponential mechanism for differentially private top-k," in International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, Proceedings of Machine Learning Research, K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvári, G. Niu, and S. Sabato, Eds., vol. 162. PMLR, 2022, pp. 7570-7582.
M. Harper and J. A. Konstan, "The movielens datasets: History and context," ACM Trans. Interact. Intell. Syst., vol. 5, no. 4, pp. 19:1-19:19, 2016.
C. R. Harris, K. Millman, S. J. van der Walt, Gommers, P. Virtanen, D. Cournapeau, E. Wieser, J. Taylor, S. Berg, N. J. Smith, R. Kern, M. Picus, S. Hoyer, M. H. van Kerkwijk, Rérard-Marchant, K. Sheppard, T. Reddy, W. Weckesser, H. Abbasi, C. Gohlke, and T. E. Oliphant, "Array programming with NumPy," Nature, vol. 585, no. 7825, pp. 357-362, Sep. 2020. [Online]. Available: https:/doi..rr/111 0000000000000111000000000---6660
M. Brett, A. Haldane, J. F. del Río, M. Wiebe, P. Peterson,

---

J. J. McAuley, C. Targett, Q. Shi, and A. van den Hengel, "Image- recommendations styles and substitutes," in Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, Santiago, Chile, August 9- 13, 2015, R. Baeza- Yates, Lalmas, A. Moffat, and A. Ribeiro-Neto, Eds. ACM, 2015, pp. 43-52.
R. McKenna and D. Sheldon, "Permute -Permute-and-Fiiii and-flip: A new mechanism for differentially private selec- tion." in Advances in Neural Information Processing Systems 33; Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, Eds., 2020.
McSherry and K. Talwar, "Mechanism design via differential privacy." in 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings. IEEE Computer Society, 2007, pp. 94-
G. Qiao, W. Su, and Zhang, "Oneshot differentially private top-k selection," in Proceedings of the 38th International Conference on Machine Learning. ICML 2021, 18-24 July 2021, Virtual Event, ser. Proceedings of Machine Learning Research, M. Meila and Zhang, Eds., vol. 139. PMLR, 2021, pp. 8672-8681.
Soumik, seoodreads-book. dataset," http://www...gggecc..../ooooooor 2019, Accessed: 2024-05-10.
T. Steinke and J. R. Ullman, "Between pure and approximate differential privacy," J. Priv. Confidentiality, vol. 7, no. 2, 2016. [Online]. Available: https://doi.orr//00 wttpg///1...00.11 2ttp:/00..1///....viiii..
'Tight lower bounds for differentially private selection," in 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, C. Umans, Ed. IEEE Computer Society, 2017, pp. 552-563.
Tamber, "Steam video games dataset," http:///www..aggcccoommmm/////aa 2016, Accessed: 2024-05-10.
J. I. Yellott, "The relationship between luce's choice axiom, thurstone's theory of comparative judgment, and the double exponential distribution." Journal of Mathematical Psychology, vol. 15, no. 2, pp. 109-144 144, 1977.
Y. Zhu and Y. Wang, "Adaptive private-k-selection with adaptive and application to multi-label PATE," in International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, ser. Proceedings of Machine Learning Research, G. Camps-Vall Valls, J. R. Ruiz, and I. Valera, Eds., vol. 151. PMLR, 2022, pp. 5622-5635. [Online]. Available: https://proceedngss.lec mlr, press/v wttpss///l//ssss22222 15/2hh222.httm
12

---

A Missing proofs
Proof for Fact F.c The proof has been implicitly suggested in our comparison with JOINT in Sec- tion 6 We reiterate it here.
We explain JOINT [Gillenwater et al. 2022) within the novel framework proposed in Section 4. which consists of the Subset Sampling and Sequence Sampling steps. Their approach assumes that
[[]] 2 ... 2 M[d] which can be achieved by sorting h. For each i E [K] and j E [d]. define
E = h[t] - M[j]. The partition they consider is equivalent to the one defined as follows:
Ung = { 8= (5(1), ...,, [h)) PD.
[| > M[ - Eig 8 = J.
Ve <i f VL >
We
[4
[|
2 Miq Eggr
Intuitively, U3 consists of the length-k sequences, 5, that satisfy: 1) the ith element in i exactly element j: 2) the first elements in have losses less than Eg and 3) the last k - elements in have losses at most Ei.
Therefore, the sequences s' U2,; share the same loss, ESOINT 8) = EGg (as defined in Equation with the first position reaching this loss being the hth position, where element j appears. Furthermore, sequences in different subsets, Ú and L can share the same loss, as it is possible that E = Jr
Next, we briefly explain how to fulfill the Subset Sampling and Sequence Sampling steps for the chosen partition.
The Sequence Sampling step is straightforward: sampling a sequence uniformly at random from U can be achieved similarly (though not identically) to the approach used in Algorithm 2 for sampling a sequence from Sr This process can be completed in ((d) time.
For the Subset Sampling step, similar to the algorithm in Section 4.1 and using Fact 3.4] sampling a
subset U1, with probability proportional to |U, exp (-e E. /2), can be achieved by computing the maximum of
{ (Xis + In (|Ubel exp (-s
- /2) (i.j) E [A] x [d]]
where X., ~ Gumbel (1). The main task is to efficiently compute |Ut.]. For each i E [k]], e [d], l [k], define
t. [ = { eld AD'l Kie] EndT/ and t. = { [d Ab' 2 āel EiJ
It can be shown that
In |Utsl= = Σ In (155119- (1) + Σ
In (4...210) - (e 1)).
RE(K-1]
Furthermore, if we define
{
i-6 j j-j
)}
E =
j' [d] AD'l > R[ - EEs
2k:
2dk
we observe that
5- أーحد 1. When e <<
i-1
i-1'
d-1
0. so En = to.j.> [9. tt.j.211 1.] Therefore, it
2k
2dk
2k
2dk
2k
2dk
On the other hand, when > i, i-t follows that
j-1' 2dk
<
1
d-1
2dk
<
0, so
In Inst
Σ In (Fal1 1))
Exi
It remains to demonstrate an efficient method for computing Tez. First, we sort the (i, [k] x [d] j
pairs in increasing order based on Ex,j +
2dk For fixed i, the values E,g for j [d] are already i for j E [d] can be obtained in (dd) time.
in increasing order, so a sorted sequence of E,, + 2k 2dg We then merge l sorted sequences in O(dk log k) time using k-way merging.
13

---

If (2.3) appears immediately after (i, in the sorted order, then In |U3 can be derived from In [U,
in (1) time. Specifically, we claim that
[4 +1,
if i if =
f 9
For the first case, assume for contradiction that there exists some + i such that &, > Consequently, there exists j' such that
(i-6_ j j-j'
i-- l
j j'
MMq - Els
>
hij'l
(14)
2k
2dk
2k
2dk
which implies that
8
h (
j'' Eey +
f
j
i
j
Eij 2k
2
Eagj
+
(15)
2dk
2k
2dk)
2k
2dk:
2k
2dk
Since the values of E
i
2dk are distinct, it follows that
2k
i
j
E 1'
>
i j
+
Ex, +
Eij
+
(16)
2k
2dk
2k
2dk
2k
2dk
which contradicts the assumption that (2,3) appears immediately after (i. in the sorted order.
For the second case (L = i) it is clear that E 2 [.] Additionally, observe that
1 j-
i i j
7 E,g
- E
2k
2dk
2k
2dk
implying that Et 2 [ Finally, we show that it is impossible for E to exceed E., [4] + 1.
If it did, then, using reasoning similar to Inequalities (14). (15), and (16). we could conclude that there exists some (i,)') that appears between (i,j) and (i,}) () which leads to contradiction.
Proof for Lemma 4.7 The proof is under the same spirit as the proof of Lemma 4.3
It suffices to show that
S2t..l IE (C+-1.) - (j - ()) (d Cr-1,)) 115 (d (j -1))
(17)
Recall Equation
12 that
||5
hen - T, Vj <i
S2n, =
3= 3- (5[1)..... sT()) E PD.
][3b]] $ h() - T, j=i
Assume we want to select sequence S2r.i. Since s(1] E (j' E [d] MDl > hup T}.
the number of possible choices for s[1] is 10 E [d] ADn > hu) - m) = 10 E [d] MD'l 2
ka) - (r - (1)1) = CT-11 The first equality holds because the A[j']] values are integers.
Since Tu is non-decreasing, for each & < j < i,
[|] > Tue)
2 fgy r, therefore
Bey E {5' E [d] Man > hi) - T}. After determining $(1..j j - 1]. 5 must be chosen from
(d) MD'l > Ag) -) \ (5(e) : < so it has Kí' E [d] M[j'] hu) 7}1 (j 1)
Cr-1,- (j- 1) choices.
Now we consider the number of choices for sTi). Since $[1], .... 3i 1 e [d] Aoj >
Th - - they do not appear (j' E [d] Maj'l s Fug - T). The number of choices for 81i] is
exactly [[ [d] Rb-' < Rao +) = d C--
For j E [i + 1. k). the number of choices for $lj]. after determining s[1..j is d - (j - 1).
Multiplying the number of choices for each element in 5 E S27,i, get
S I[ (Cr-13 - (j 1)) (d C,-1,) 11 (d (j -1))
14

---

B Implementation Details
In this section, we discuss how to implement the Subset Sampling and Sequence Sampling steps, according to the partition {S,, E [0.. 11, [k]] U [S 2n,ii : [k]]] induced by the loss EAA-
B.1 Subset Sampling
The algorithm is in Algorithm
Computing the C..- Let fx= - 2 be the function given by fg[t] = {i e D: v) By using standard hash map, fī can be computed with ((d) time and space. Based on the definition of the Or and that h consists of only integer scores, the following recursion holds.
Co.1 (a(h(a))
Co.s CoJ-1 = fx (Frs))
1 ()
AA vi<jsk, h vl<r<>
(18)
Cr.j Cr-15 = =Ifx(mG)) - -r)
Therefore, Crg can be computed in Old rk) time.
Computing In |S, and In [S2r,l To simplify the notation, we apply the following definitions. Definition B.1.
Sri ifr < 7
8,
(19)
S2tmi if
(Cri
ifr <
Cri.
(20)
dl =-
For each E [0...] and each i [1 kt), define the prefix and the suffix sums
ā|r [] = Σ} In (Cr-1. (j 1)), 8 o|r Σ In (Cru -j - Vi E [k].
(21)
For convenience, we assume o|.,0) = 3| A: + 1] = 0. Combining Equation and 13 we have
In S Ø[r In (C.,: C,-1a) + + 1]
(22)
corner case is = 0. By definition, |Sa. = 0 unless i = 0. We can set Č- 1,0 = 0 and the equation still holds.
Algorithm Subset Sampling
Input: Histogram To; Privacy Parameter
1: Compute fg N + 2 s.t. fF((] = (i E D: Mid = f), Vt E N.
2: Compute the Cr,y's according to Equation (88 and Equation 20
3: Compute the ø's and ō's according Equation 21
4: Compute the In SS,: 's according to Equation (22)
5: Sample (r, i) + arg max (Xr,, + In (IS,xl exp (-E r/2))) }. where X, Gumbel (1)
6: return (r,
B.2 Sequence Sampling
The algorithm for sequence sampling is Algorithm 2 follows from the counting argument in Lemma when r < r and Lemma when
Lemma B.2. Algorithm can be implemented in O(d) time.
15

---

Algorithm 2 Sequence Sampling
Input: (r; Ensure: g g+" Sp,
1: Let 5 4- Ø be an empty length-k array
2: for j f- 1 to 1 do
3: Sample $[] - {e D: Miq > Muy - r} ( -0- 1}}
(LED: D: hig h() - r), <
4: Sample an 8]j]
{LE D: hie < b()) - T). ifr=
5: for
do
(LED: Al - (51))..... .1............. -1j-111 1]}, ifr <T D 1|}
6: Sample an [
=f
7: return
Proof of Lemma B.2 ones.
We discuss different sections pseudo-codes of Algorithm 2 start by the easy
Case 1: Algorithm
2 line Clearly, this can be implemented in ((d) time.
Case Algorithm line when r= T. After the first i entries of ø are determined, we can create an dynamic array, denoted ã, consisting of elements 2> \
...,,,.............. 3Ti]]. [ This takes (dd)
time. Sampling and removing an item from Ø can done in O(1) time via standard technique, as described in Algorithm (the A-()) procedure).
Case III: Algorithm 2 line
This section can be implemented in Old + (k + 7) log(k: 7)) time, as described in Algorithm (the efficient sequence sampler procedure). It first computes a function
fg. NN + 2%, s.t., ft(() {i E D hi]]] t). Vt N. By using standard hash map, fg can be computed with (d) time and space. Then it finds the set
{t N: fx(t) # Ø At > h(x) - T}. and store elements in I as an array. can be computed in (dd) time. Since an item in must equal one of the values of Ti()).... (ig)) Figs - 1, 1,..., hig - T + 1, it is easy to see that [ S k - r. So sorting the items in I in decreasing order takes O((k + r) log(k: + 7)) time. Then the algorithm create empty dynamic array ă, and variable POS = 0. For each j E (i 1]. before the sampling step (Algorithm 3 line 18), we claim the following holds:
* POS arg max, [[z] > hg)
ā (EE D: Mie huy r) \
$15 1]}
This is true for j = 1. Now, assume this is true for the j and consider the case for + 1. After the sampling step (Algorithm 3
line 18 in the jth iteration, we have POS arg max, I[z] >
Trg - r and ū = (e E D : he h - r} {5[1).... [(j])...,,,,])) At the (j + 1)-th iteration, the
inner loop (Algorithm 3 lines 15 increases POS from 21 - arg max, I[z] hgy) r) to
22 arg max; -[2] > h(+1) r, and expand ă correspondingly. Since [I[zz].... ... I [|22]] contains
all t [h(+1) - r 1, 1.) - r] s.t., (t) # Ø. after this, ă becomes
TEDD T U
ā = EE {eED: D: :MA > Fng - -
r} \ (511)....,1111)
SR(!)
= ffE LE D: Mie > n - r) (611)...,,,,11)
EE [d] (ho) - h]e] > RG+D) -r] -r]
= {EED: D: Mi > T J - : (511)...,,111
Therefore the invaraints are maintained.
16

---

Case IV: Algorithm 2 line 5 6
when r < T. Observe that {eE E D kie 2 h6) - = {eE ( D:
h[q h6)) - - 13. Hence we can use similar sampling technique to Case III.
Algorithm 3
1: Procedure ARRAY SAMPLER AS(a)
Input: Dynamic array
2:
t- length of a
3: Sample I x- [Z]
4:
Swap a[/] and [[L]
5:
[[L]] Remove a[]] from á
6:
7:
return ans.
8: Procedure EFFICIENT SEQUENCE SAMPLER
Input: Histogram h;; Parameter i [k].
Compute the function fú; :N + 2Nd s.t, fR(t) ( E : - WEN
9:
10:
Compute I + {t e N: (t) * A t h()) 7 and store it as array
11:
Sort I in decreasing order
12:
ă <- empty dynamic array
13:
POS 0
14:
for + 1 to -1 do
15:
while POS < length of A I[POS + 1}> nog - r do
Add the items f [I[POs + 1J) to the back of ā POS POS +
18:
$1 + as
19:
return s11]...., 1].
B.3
Vectorization
Though FASTJOINT is not implemented yet fully vectorized, discuss its potential here. Given that FASTJOINT has a runtime O(d + k2/E /E- Inn),, the bottleneck lies the O(d) component for large datasets.
The first (d) part involves computing the groups fx(() = (i E D M|] = 1) for each unique value in h. This computation could be vectorized using an appropriate library.
The second (dd) component in Sequence Sampling can be eliminated with careful implementation. Recall that in Algorithm 2 crucial step is to sample elements uniformly at random from the set
(E E D: M[{ Juo - r (511), sTj 1]}.
(23)
for a possible value of E (1, .). Sampling from the set {e E D Mi 2 Fuy { ø - }}} can be handled similarly.
r}
To achieve this, we construct an array of at most l + buckets (the cost of constructing this array is covered by the initial (d) time cost):
[g fg Fgl ... ......ggliii (0))) fg Fg 1J. 1,0m) r]]-
Assume that each fr [t] this array is itself managed by a dynamic array. Sampling from 23 is then equivalent to sampling uniformly from prefix of buckets without replacement.
The sampling process involves first selecting a bucket with probability proportional to its size, then drawing element uniformly at random from that bucket. After sampling, the chosen element is removed from the bucket, which can managed efficiently using a dynamic array. This approach removes the dependency d in the sampling step.
17

---

C
Supplementary Plots
In this section, we provide supplementary plots for our experiments:
Figure
illustrates the gaps between large-score items for all tested datasets.
Figure
displays the algorithm's 's rumning time, lo error, and & error versus
Figure
showcases the algorithm's 's running time, foc eтror, and { error versus B.
Figure
depicts the running time of JOINT (excluding time from the Sequence Sampling step) versus the running time of proposed algorithm FASTJOINT (including time from the Sequence Sampling step), over all tested datasets. Given this, our algorithm still runs orders of magnitude faster than JOINT. Due time constraints, we only repeated the experiments 5 times generate the plots. This is acceptable since, according to the previous experiments, the running time of the algorithms is quite stable.
games
books
news
10a
10a
10a
count diff
count ciff
clff
10a
10a
10a
10a
10:
10a
107
10a
0
100
200
300
100
200
300
100
200
300
tweets
movies
food
10
10a
10a
caunt diff
count diff
10¹
10?
count
102
102
104
10a
10a
109
100
200
300
100
200
300
100
200
300
Figure 4: The gaps between the top-k scores (for k: = 300) for all tested datasets.
18

---

10a
10
10
time (5)
error
4, error
10-2
10a
10-1
10a
books
books
books
10a
10-1
10
time (6)
error
4: error
10a
10-2
10
10a
-0
109
100
2
10a
104
103
10-1
error
10
4 error
102
10-1
10a
104
10
10a
0-
100
2
10a
10a
10a
10a
10-1
error
error
10a
10-1
10
10t
10a
100
10a
10a
104
103
10-1
error
10a
1. error
10a
10a
10-2
10a
10a
10a
2
food
10a
10
(4)
10a
1- error
4 error
10a
10-1
10a
16a
10-2
2
.....
Fastjoint
Joint
CDP Peel
PNF Peel
Figure 5: Left: Running time vs E.
Center: for eтror E. Right: l error vs
The flo plots are padded by 1 avoid log 0 the y-axis.
19

---

800
25000
10 1
20000
time (5)
error
600
10-2
15000
400
10000
200
10-4
10-3
10-2
10
10
10
books
books
books
10
time (S)
4 error
10-2
5-
2-
10-1
0
10
10
10
10
10
10-4
10
news
news
news
10a
300
1200
1000
(6)
10-4
150
600
100
400
50
200
10
10
10
10
10
10-3
10-2
10
10
10-2
tweets
tweets
tweets
1200
1000
800
10
error
400
10
200
10
10
10
10
10
10
10
10
10
movies
movies
movies
10P
3000
10
error
error
2000
10-2
1000
10-1
10-1
10
10 -1
10-3
10-2
10-1
10
10-2
food
food
food
1250
60000
1000
error
f1 error
750
40000
10-1
500
20000
10-1
250
4
3
10
10
10
9
.....
Fastjoint
Joint
CDP Peel
PNF Peel
Figure 6: Left: Running time vs B. Center: loo error B. Right: error 8.
The E, /lo plots are padded by 1 to avoid log 0 on the y-axis.
20

---

games
10-1
10-1
10-1
time (5)
time (s)
time (5)
10-2
e331
10
2x281
100
150
200
10
10
books
books
books
time (5)
10-1
time (5)
10-1
time (s)
10:2
10
50
100
150
200
2
3
10
10
news
news
news
10a
10a
time (S)
time (s)
time (5)
10-1
10:11
10-1
10a2.
50
100
150
200
10
10
10
tweets
tweets
tweets
10a
109
time (5)
time (s)
time (s)
10-1
10-1
10-2
10
100
150
200
2
3
10
10
10
movies
movies
movies
10a
10a
109
time (3)
time (S)
time (5)
10-1
10-1
10-1
10-2
200
10-4
10
10
food
food
food
101
10a
time (s)
109
time (s)
time (5)
10a
10
10-1
10-1
10
10
8
G Fastjoint
Joint
Figure 7: Left: Running time vs k.
Center: Running time vs E. Right: Running time vs B.
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We have written the abstract and introduction carefully.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss them in the experiment section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
22

---

Justification:
Missing proof' are provided in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We provide links public datasets, and will provide our codes.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
23

---

Answer: [Yes]
Justification:
We use public datasets and will provide our code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
lc for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ccpppp.ccppulli//guiii wwwiicccguie//eeeeeeeeeis CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Parameters are provided in the experiment seating section. Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Error metrics are provided in experiment setting section.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
24

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
Experiment environment is reported in the paper.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httt:p////aarrrg..cccaaaa//////p
Answer: [Yes]
Justification:
We don't 't have human subjects nor participants.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., - if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The goal of this work is to advance of theoretical nature. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted.
data analysis and is
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
25

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We have made proper citations.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
26

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We include detailed READ-ME file.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
27


Reviews:
[{"review_id": "WCLwd8VjNM", "reviewer": "Reviewer_u5C6", "summary": "This paper gives a faster method of performing differentially private top k selection. Previous work by Gillenwater et al., introduced the joint exponential mechanism in the context of top k selection and gave a DP algorithm that used \\tilde{O}(kd) time and space. The main contribution of this paper is a new sampling technique which uses a variant of the joint exponential mechanism and improves the time and space to \\tilde{O}(d+k^2).", "questions": "I don't have any specific questions, just a suggestion to add more background on the Joint Exponential Mechanism in the appendix since you are building on this framework.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem addressed by the paper is an important one, and the results are novel and improve upon the state of the art. Overall I think the paper does a decent job of comparing and contrasting their techniques with that of the previous work. The subsampling and pruning techniques are quite effective and have been described adequately well in the main body. The experiments support claims made in the paper.", "weaknesses": "Since the paper builds on the Joint exponential mechanism from previous work, it would be helpful to have a more detailed supplementary section about this in the appendix for e.g. to give more background.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the suggestion. \nWe will add more background on the Joint Exponential Mechanism in the appendix. \nSpecifically, we will include brief explanations and proofs for the properties of the Joint Exponential Mechanism (Facts 3.5 and 3.6) to ensure completeness.", "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": "lu7VN0BZtS", "reviewer": "Reviewer_3vYL", "summary": "This paper studies differentially private top-k selection i.e., selecting the top k sums from a set of d different ones. This problem has been well studied and mechanisms achieving asymptotically optimal error are known. Durfee and Rogers [2019] gives an optimal mechanism that takes O(d) time. However, in 2022, Gillenwater et al. proposed an alternate mechanism based on the exponential mechanism directly run on the set of all sequences of length k, and showed that it achieved better empirical performance on many datasets. While naive implementations can take exponential time, they showed how this algorithm can be implemented in time O(dk). \n\nIn this paper, the primary focus is on improving the computational complexity of the algorithm described by GIllenwater et al. to $O(d + k^2)$ which matches the Durfee et al. time complexity for most $k$ of practical interest. \n\nTheir general framework involves partitioning the sequence space (such that every subset in the partition has identical quality), and performing a two step sampling- firstly, sampling a subset in the partition as per the exponential mechanism and then outputting a uniformly random element in the subset. The partition consists of subsets $S_{r,i}$ ($r$ denotes the error and $i$ a coordinate) consisting of sequences where the first coordinate achieving the error $r$ is $i$. They show that using a recursive approach, with $O(d)$ preprocessing time, the subset sampling can be performed in $O(nk)$ time and the uniform sequence sampling in $O(d)$ time. Finally, since with high probability the exponential mechanism does not sample a sequence with error larger than $O(k)$, by truncating the score function used in the exponential mechanism (i.e. max error) to never be larger than $k$, the time complexity of the algorithm can be reduced to $O(d+k^2)$. They also back up their theoretical results with experimental work confirming their findings.", "questions": "I had a couple of questions about the experiments:\n\n1) On the movies dataset, the FastJoint algorithm shows larger variance than other methods (and also more than FastJoint on other datasets). I'm curious why this might be.\n\n2) For the food dataset, the sudden drop in variance of the error of FastJoint close to k=100 seems very strange- what happened here?\n\n3) For small datasets, is there any hope to utilize the benefits of vectorization for FastJoint as well? Some comment may be nice.", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1) Top-k selection is a fundamental problem that abstracts many important optimization tasks. Hence, more efficient implementations of the algorithms achieving the best empirical accuracy for this problem are valuable contributions.\n\n2) Improving the time complexity of the algorithm requires a novel partitioning approach. As argued by the authors, fitting the previous Gillenwater et al. approach into the same partitioning framework does not allow for the time complexity improvement that comes from truncating the score function.\n\n3) The paper is well written and thorough and the experimental work explains clearly where we can expect the improved FastJoint algorithm to be better than other algorithms described for this problem.", "weaknesses": "The paper doesn't have any weaknesses that I can pinpoint.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for being supportive of our manuscript.\n\n\n\n1. On the movie dataset, the JOINT (orange color) has a larger variance than FastJOINT (green color). \nIn this dataset, there is a visually noticeable variation in the error plot around $k = 100$ (Figure 1). \nHowever, this variation is actually small, ranging between $10^0$ and $10^1$ on the $y$-axis.\n\n\n\n\n2. We check the original experimental data for the food dataset. The loss does not drop after $k \\ge 100$; it remains roughly the same. Indeed, if we create a screenshot of Figure 1 for the food dataset and draw a horizontal line near the $\\ell_\\infty$ error plot of FastJoint, we can see that the error plot of FastJoint is parallel to the horizontal line.\n\n\n    The reason that the error remains stable can be related to the fact that the gap between the $k^{\\text{th}}$ and $(k + 1)^{\\text{th}}$ largest counts becomes small and stable after $k \\ge 100$ (which can be seen from the plots of the gaps in Figure 4 on page 16 in the appendix), and that FastJoint's error is gap-dependent.\n\n\n\n3. The only $O(d)$ time part of the algorithm is computing the histogram of the score, which can be easily vectorized. \nWhile the rest of FastJoint is hard to vectorize, it is not the time bottleneck when running on an industrial dataset (e.g., $d = 10^8$, $k = 100$).", "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": "9uKDNIQbAB", "reviewer": "Reviewer_pna3", "summary": "This paper considers a core differentially private primitive of top-k selection. In this problem, there are $d$ items where each item gets a frequency $h[i]$ which is the sum of $n$ binary vectors $\\{0,1\\}^d$. The goal is top select (approximate) top-k most frequent items while preserving privacy with respect to the addition or removal of a single vector (corresponding to a user's contribution).\n\nThe paper begins by calling attention to a recent work of Gillenwater et al. which achieves good empirical performance for this problem via the exponential mechanism using an algorithm called Joint. The algorithm assigns a score to every possible $\\binom{d}{k}$ subset. In order to efficiently implement sampling proportionally to the exponentiation of the score, the Joint algorithm considers different level sets of subsets which can be efficiently sampled from. The total running time of this algorithm is $\\tilde{O}(dk)$.\n\nIn this work, the authors give a faster algorithm that implements (essentially) the same exponential mechanism algorithm that runs in time $\\tilde{O}(d + k^2/\\epsilon)$. The main idea of the algorithm is to truncate the score function to be at most a certain value which allows for faster computation without worsening the quality of the algorithm by much.", "questions": "- Is the $O(d + nk)$ time version of the algorithm before pruning already new in this work?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The problem is well-motivated and important within differential privacy.\n- The proposed change to prior work is simple and yields a significant benefit in the theoretical bounds.\n- The experiments are detailed and show across the board that the new algorithm is much faster than Joint while retaining its performance, which is often better than other baselines.", "weaknesses": "- It is not entirely clear to me what part of section 4 is novel in this paper and what part comes from the prior work of Gillenwater et al. See my questions below. Is the setup of subsets from which to sample different from Gillenwater in addition to the loss function? Or is it only truncating the loss function that yields the benefits in the paper?\n- Include $\\epsilon$ in the running time. Especially as it only appears for the final version of your algorithm and not elsewhere, it is important when comparing runtimes.\n- Minor: Order the references alphabetically.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the suggestion. We will order the reference list alphabetically in the final version, and include the $\\varepsilon$ in the running time.\n\nWe will also clarify our contribution at the beginning of Section 4 in the final version:\n\n1. Section 4.1 is novel. It includes\n\n   * a new \"group by\" framework for sampling a sequence from the space comprising all $d^{\\Theta(k)}$ possible length-$k$ sequences directly;\n     \n   * a new partition for the sampling space, which leads to the $O(d + nk)$-time algorithm; and\n  \n     \n   * a new pruning technique (by truncating the loss function), which reduces the running time to $O(d + \\frac{k}{\\varepsilon} \\cdot (k\\ln d + \\ln\\frac{1}{\\beta}))$.\n\n\n3. Section 4.2 compares our approach with the one by Gillenwater et al. To facilitate the comparison, we explain Gillenwater et al's algorithm using our newly proposed framework. Note that they applied a different partition of the sampling space, and our pruning technique does not work for their partition.", "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": "D9EmFuGgKM", "reviewer": "Reviewer_owmk", "summary": "The paper presents a compute and memory efficient implementation of the differentially private top-$k$ algorithm proposed by Gillenwater et al. (2022) which is based on applying the exponential mechanism to all index sequences of length $k$. The implementation by Gillenwater et al. (2022) has the time complexity $O(d k \\log k + d \\log d )$ and space complexity $O(dk)$, where $d$ is the number of items, whereas this method has the complexity $\\widetilde{O}(d + k^2)$, where $\\widetilde{O}$ omits the log factors. The experimental comparisons on various datasets verify that this method gives the same utility as the method by Gillenwater et al. (2022) and has 1-2 orders of magnitude smaller running time.", "questions": "Could you answer these questions ( I am ready to reconsider my score ):\n\nWhen is this impementation really needed? Are you thinking of an online setting? If yes, would the speed be enough for the online setting (considering that the online requirements are often in the order of milliseconds) ? Why not to use CDP Peel if it is so much faster and when is it better?\n\nMinor comments:\n\n- p.1, line 31: \"the its\"\n- p.3, line 96: \"lose function\"\n- p.3, Equation 4: Please add some definition/explanation of $s$\n- p.5, line 177: \"is decreases\"", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "- The paper is very well written, in particular the motivation and introduction to the topic\n- Clear contribution to an existing method that is in some sense state-of-the-art (has the best accuracy over other baselines in some of the cases)", "weaknesses": "- Fairly narrow contribution after all, as it seems that the only contribution is to reduce the memory consumption and compute time of an existing method. The reduction is big but does not reach the speed of the baseline method \"CDP Peel\" by Rogers et al. (2019) which has also better utility in a large part of the datasets. CDP Peel seems to be the only one of the baseline methods that reaches the speed of the order of milliseconds or less on a standard CPU. And, in most cases, the baseline implementation by Gillenwater et al. (2022) is already quite fast (much less than a second).\n\n- Related to the above comment: there is kind of missing the bigger picture, like when is this implementation useful? When is it useful to use this method vs. CDP Peel?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the suggestions. We will provide a clearer overview of the comparison between the approaches in the final version.\n\n1. When there is a large gap between the $k^{\\text{th}}$ and $(k + 1)^{\\text{th}}$ largest counts, FastJOINT (our algorithm) and JOINT (by Gillenwater et al. 2022) can achieve smaller empirical error than CDP Peel. This finding is consistent with Gillenwater et al. (2022).\n\n2. JOINT has $O(dk \\log k + d \\log d)$ time usage and space usage of $O(dk)$. Even in the offline setting, it suffers from scalability issues. Our approach, FastJOINT, reduces both running time and space to $O(d + \\frac{k^2}{\\epsilon} \\cdot \\ln d)$ while providing similar empirical error. It offers a speedup compared to JOINT for free.\n\n3. JOINT is slow in our experiments. For example, on the food dataset ($d \\approx 0.16 \\cdot 10^6$, $k = 200$), it took more than 40 seconds. Given this observation, we can anticipate extremely long running times for JOINT on larger datasets, such as those with $d = 10^8$.", "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:
We thank all the reviewers for their consideration of our manuscript and their constructive feedback.

Meta-review: The reviewers remark that the manuscript studies an important/fundamental problem [u5C6, pna3, 3vYL], makes a novel/non-trivial contribution [u5C6, 3vYL, owmk, pna3] which is a clear improvement upon the state-of-the-art [u5C6, owmk], explanations are clear / paper well-written [u5C6, 3vYL, owmk] and experiments substantiate claims [u5C6, 3vYL, pna3], but it could be clearer which parts can be implemented with vector-wise operations [3vYL], which sections are novel [pna3], it would be useful to provide a bit more background on the joint exponential mechanism [u5C6] and considering that the main contribution are improvements in sampling speed & memory usage, how big the advantage is over CDP peel that is even more efficient [owmk].

The rebuttal answers reviewer questions, agrees to add more background on the joint exponential mechanism [response to u5C6], clarifies that section 4.1 is novel [response to pna3] and which parts can be vectorised [response to 3vYL] and clarifies advantages over CDP peel and contextualises it within the propose-test-release approach [response to owmk].

The overall recommendation is to accept the submission with the changes agreed upon in the discussion phase as the proposed approach mitigates one major drawback of the joint exponential mechanism, i.e., sampling efficiency, without sacrificing utility, offers good insights and ideas relevant to the problem and the manuscript substantiates claims appropriately.
Decision: Accept (poster)