Faster Differentially Private Top-$k$ Selection: A Joint Exponential Mechanism with Pruning

Authors: hao  wu
hanwen  zhang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 19:06:01

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.

Main paper: 
 introduction: 
 Top-k selection is a fundamental operation with a wide range of applications: search engines, ecommerce recommendations, data analysis, social media feeds etc. Here, we consider the setting where the dataset consists of d items evaluated by n people. Each person can cast at most one vote for each item, and vote for unlimited number of items. Our goal is to find a sequence of k 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 on top-k algorithms that are differentially private (Dwork et al., 2006) : it is 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 be and how efficient they are.Significant progress has been made in understanding the theoretical boundaries. There are approximate differentially private algorithms (Durfee and Rogers, 2019; Qiao et al., 2021) that achieve asymptotic accuracy lower bound (Bafna and Ullman, 2017; Steinke and Ullman, 2017) , and have O(d) time and space usage.There is also a research endeavor aimed at enhancing the empirical performance of the algorithms. A particularly noteworthy one is the JOINT mechanism by Gillenwater, Joseph, Medina, and Diaz (2022) , 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 k times-the JOINT mechanism considers the sequence holistically, directly selecting an output from the space comprising all d Θ(k) possible length-k sequences.While the algorithm has running time and space Õ(dk), successfully avoiding an exponential time or space consumption, it notably incurs a higher computational cost than its O(d) counterparts. This prompts the interesting question: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 + k 2 /ε • ln d) This is an informal statement of Theorem 4.1. When k ∈ O( √ d) (a common scenario in practical settings), the time and space complexity simplifies to Õ(d). 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, we introduce a pruning technique to handle outputs with low accuracy uniformly. This technique effectively reduces the number of subsets to Õ(k 2 ), leading to an algorithm in Õ(d + k 2 ) time and space complexity.Finally, we perform extensive experiments to • Verify the theoretical analysis of our algorithm.• Demonstrate that our algorithm runs 10-100 times faster than JOINT on the tested datasets.• Show that our algorithm maintains comparable accuracy to JOINT.Organization. Our paper is structured as follows: Section 2 formally introduces the problem, while Section 3 delves into the necessary preliminaries for our algorithm. Section 4 introduces our novel algorithm, and Section 5 presents our experiment results. 
problem description: 
 Let D . = {1, . . . , d} be a set of d items and U . = {1, . . . , n} be a set of n clients. Each client v ∈ U can cast at most one vote for each item, and can vote for an unlimited number of items. For each item i ∈ D, its score ⃗ h [i] is the number of votes it received. The histogram is a vector ⃗ h . = ( ⃗ h[1], . . . , ⃗ h [d] ) ∈ [0 . . n] d . Define P D,k . = (i 1 , . . . , i k ) ∈ D k : i 1 , . . . i k are distinct be the collection of all possible length-k sequences.The differentially private top-k selection problem aims at finding a sequence from P D,k with approximately largest scores, while protecting the privacy of each individual vote.Privacy Guarantee. Two voting histograms ⃗ h, ⃗ h ′ ∈ N d are neighboring, denoted by ⃗ h ∼ ⃗ h ′ , if ⃗ h ′ can be obtained from ⃗ h by adding or removing an arbitrary individual's votes. Therefore, when ⃗ h ∼ ⃗ h ′ , we have || ⃗ h -⃗ h ′ || ∞ ≤ 1, and ⃗ h ≤ ⃗ h ′ or ⃗ h ≥ ⃗ h ′ . To protect personal privacy, a top-k selection algorithm should have similar output distributions on neighboring inputs. Definition 2.1 ((ε, δ)-Private Algorithm (Dwork and Roth, 2014) ). Given ε, δ > 0, a randomized algorithm M :N d → P D,k is called (ε, δ)-differentially private (DP), if for every ⃗ h, ⃗ h ′ ∈ N d such that ⃗ h ∼ ⃗ h ′ , and all Z ⊆ P D,k , Pr[M( ⃗ h) ∈ Z] ≤ e ε • Pr[M( ⃗ h ′ ) ∈ Z] + δ .(1)Remark: An algorithm M is also called ε-DP for short, if it is (ε, 0)-DP. If an algorithm is ε-DP, it is also called pure DP, whereas it is called approximate DP if it is (ε, δ)-DP.Although we present the definition in the context of top-k selection algorithms, it applies more generally to any randomized algorithms M : X → Y, where X is the input space, which is associated with a symmetric relation ∼ that defines neighboring inputs.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 are not discussed in the paper. • The authors are encouraged to create a 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 on 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 a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not 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 to address problems of privacy and fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
exponential mechanism: 
 The exponential mechanism (McSherry and Talwar, 2007 ) is a well-known differentially private algorithm for publishing discrete values. Given a general input space X (associated with a relation ∼ which defines neighboring datasets), a finite output space Y, the exponential mechanism M EXP : X → Y is a randomized algorithm given byEQUATIONwhere E EXP : X × Y → R is called the loss function measuring how "bad" y is when the input is x, and ∆ EXP is the sensitivity of E EXP which is the maximum deviation of E EXP :EQUATIONFact 3.1 (Privacy (McSherry and Talwar, 2007) ). The exponential mechanism M EXP is ε-DP.Fact 3.2 (Utility Guarantee (McSherry and Talwar, 2007) ). For each β ∈ (0, 1), and τ .= 2•∆EXP ε • ln |Y| β , the exponential mechanism M EXP satisfies Pr [E EXP (x, M EXP (x)) ≥ min y∈Y E EXP (x, y) + τ ] ≤ β, ∀x ∈ X .Implementation. Given input x ∈ X , a technique for implementing the exponential mechanism is to add i.i.d. Gumbel noises to the terms of {-ε • E EXP (x, y) / (2 • ∆ EXP ) : y ∈ Y}, and then select the y corresponding to the noisy maximum. Definition 3.3. Given b > 0, the Gumbel distribution with parameter b, denoted by Gumbel (b), has probability density function p Yellott, 1977) ). Assume that w i ≥ 0, for i ∈ [m], and(x) = 1 b • exp -x b + exp -x b , ∀x ∈ R. Fact 3.4 ((X i ∼ Gumbel (1) , i ∈ [m] are independent random variables. Then Pr i = arg max j∈[m] (X j + ln w j ) ∝ w i .It follows that, if X y ∼ Gumbel (1) , y ∈ Y are independent random variables, thenPr y = arg max y ′ ∈Y {X y ′ -ε • E EXP (x, y ′ ) / (2 • ∆ EXP )} ∝ exp -ε • E EXP (x, y) / (2 • ∆ EXP ) .The JOINT mechanism M JOINT : N d → P D,k (Gillenwater et al., 2022) is an instance of the exponential mechanism which samples a sequence ⃗ s = (⃗ s[1], . . . , ⃗ s[k]) directly from P D,k , with the loss functionEQUATIONwhere ⃗ h (i) is the true i (th) largest entry in ⃗ h. It can be seen that E JOINT (•) has sensitivity ∆ JOINT = 1.Observe that a naive implementation of this exponential mechanism needs evaluating and storing the scores of Gillenwater, Joseph, Medina, and Diaz (2022) demonstrate that the exponential time and space requirements can be reduced to polynomial. Fact 3.5 (JOINT Mechanism (Gillenwater et al., 2022) ). There is an implementation of exponential mechanism which directly sample a sequence from P D,k according to loss function|P D,k | = d Ω(k) sequences. Remarkably,E JOINT ( ⃗ h, ⃗ s) = max i∈[k] ⃗ h (i) -⃗ h ⃗ s[i] ) with time O(dk log k + d log d) time and space O(dk).For completeness, we includes a short proof of Fact 3.5 in Appendix A. Let ⃗ s * corresponds to the k items with the largest scores. Then clearlymin ⃗ s E JOINT ( ⃗ h, ⃗ s) = E JOINT ( ⃗ h, ⃗ s * ) = 0. Combining |P D,k | = d k • k! and ∆ JOINT = 1, and applying Fact 3.2, provide the theoretic utility guarantee of JOINT.Fact 3.6 (Utility Guarantee). For each β ∈ (0, 1), τ .= 2 ε • ln ( d k )•k! β ∈ Θ k ε • (k ln d + ln 1 β ) , Pr[E JOINT ( ⃗ h, M JOINT ( ⃗ h)) ≥ τ ] ≤ β.(5)Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes]• 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 a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
algorithm: 
 In this section, we present an algorithm which has similar output distribution as the JOINT mechanism (Gillenwater et al., 2022) , but reduces the time and space complexity to O(d + k • τ ). The main result is stated as follows.Theorem 4.1. Let β ∈ (0, 1), τ .EQUATIONEQUATIONwhere E A ( ⃗ h, ⃗ s) .= min (E JOINT ( ⃗ h, ⃗ s), τ ), and ∆ A is the sensitivity of E A . Then A is ε-DP and has an implementation with time and space complexity O(d + k • τ ). It satisfies the following condition:Pr[E JOINT ( ⃗ h, A( ⃗ h)) ≥ τ ] ≤ β. (7) Simplification. When 1/β ∈ O d k , the error τ reduces to O(d + k 2 /ε • ln d).It can be verified that the sensitivity ∆ A = 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 of E A (and directly applying Fact 3.2), we express it in terms of the loss function E JOINT . The error achieved mirrors that of JOINT, as stated in Corollary 3.6. A detailed comparison with JOINT is deferred to Section 6, 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 is clear from the context, we use E(⃗ s) as shorthand for E JOINT ( ⃗ h, ⃗ s), and E A (⃗ s) as shorthand for E A ( ⃗ h, ⃗ s).Partitioning. We begin with a novel framework for designing algorithms that produces the same output distribution as JOINT. Let P 1 , . . . , P m be an arbitrary partition of P D,k . It is called Econsistent, if all sequence belonging the same subset have the same loss (w.r.t loss functionE): ∀i ∈ [m], ∀⃗ s, ⃗ s ′ ∈ P i , E(⃗ s) = E(⃗ s ′ ).We regard E(P i ) as the loss of the sequences in P i . Given this partition, we can design an algorithm that reproduces the output distribution of JOINT using a two-step approach:Subset Sampling: sample a subset P i with probability proportional to|P i | • exp (-ε • E(P i )/2).Sequence Sampling: sample an ⃗ s ∈ P i uniformly.There can be more than one choices of partitions of P D,k . We would like to find one which enables efficient sampling algorithms for both steps. We first consider the partition S r,i , r∈ [0 . . n], i ∈ [k],given by:EQUATION)Based on the definition of E in Equation (4), S r,i represents the subset of sequences with an loss equal to r, and i denotes the index of the first coordinate reaching this loss. Hence, E(S r,i ) = r. Via Fact 3.4, to sample an S r,i with probability proportional to |S r,i |•exp (-ε • r/2), we can compute the maximum of X r,i+ ln |S r,i | • exp (-ε • r/2) : (r, i) ∈ [0 . . n] × [k] , where X r,i ∼ Gumbel (1).The first key advantage of the partition being discussed is that, each ln |S r,i | can be expressed as a sum of k terms and it can be computed efficiently.Definition 4.2. For each r ∈ [0 . . n], j ∈ [k], define C r,j . = |{j ′ ∈ [d] : ⃗ h[j ′ ] ≥ ⃗ h (j) -r}|. Lemma 4.3. For each r ∈ [0 . . n], i ∈ [k], it holds that ln |S r,i | = i-1 j=1 ln (C r-1,j -(j -1)) + ln C r,i -C r-1,i + k j=i+1 ln (C r,j -(j -1)).(9) Lemma 4.4. For all r ∈ [0 . . n], j ∈ [k], C r,j can be computed in O(d + nk) time. Furthermore, given the C r,j 's, for all r ∈ [0 . . n], ln |S r,i | can be computed in O(nk) time.The algorithms for proving Lemma 4.4 are detailed in Appendix B. At a high level, for a fixed r, the C r,j , j ∈ [k] constitute a monotone sequence, enabling us to devise a recursion formula to compute them. Additionally, the prefix sums (the first term) and the suffix sums (the last term) in Equation ( 9) can be pre-computed, simplifying the computation of ln |S r,i | to adding only three terms.Here, we present a proof for Lemma 4.3, offering insights into the structure of S r,i .Proof for Lemma 4.3. It suffices to show thatEQUATION)The proof is via standard counting argument: assume we want to select a sequence ⃗ s ∈ S r,i . Since⃗ s[1] ∈ {j ′ ∈ [d] : ⃗ h[j ′ ] > ⃗ h (1) -r}, the number of possible choices for ⃗ s[1] is |{j ′ ∈ [d] : ⃗ h[j ′ ] > ⃗ h (1) -r}| = |{j ′ ∈ [d] : ⃗ h[j ′ ] ≥ ⃗ h (1) -(r -1)}| = C r-1,1 .The first equality holds because the ⃗ h[j ′ ] values are integers.Next, since ⃗ h (1) ≥ ⃗ h (2) , it also holds that ⃗ s[1] ∈ {j ′ ∈ [d] : ⃗ h[j ′ ] > ⃗ h (2) -r}. After determining ⃗ s[1], the number of choices for ⃗ s[2] is |{j ′ ∈ [d] : ⃗ h[j ′ ] > ⃗ h (2) -r}| -1 = C r-1,2 -1. Continuing this argument, for each j ∈ [1 . . i -1], the number of choices for ⃗ s[j], after determining ⃗ s[1 . . j -1], is |{j ′ ∈ [d] : ⃗ h[j ′ ] > ⃗ h (j) -r}| -(j -1) = C r-1,j -(j -1).Now we consider the number of choices for ⃗ s[i]. Since ⃗ s[1], . . . , ⃗ s[i -1] ∈ {j ′ ∈ [d] : ⃗ h[j ′ ] > ⃗ h (i) -r}, they do not appear in {j ′ ∈ [d] : ⃗ h[j ′ ] = ⃗ h (i) -r}. The number of choices for ⃗ s[i] is exactly |{j ′ ∈ [d] : ⃗ h[j ′ ] = ⃗ h (i) -r}| = C r,i -C r-1,i .The cases for j ∈ [i + 1 . . k] are similar to the cases of j ∈ [1 .. i -1]. Since ⃗ h (1) ≥ ⃗ h (2) ≥ • • • ≥ ⃗ h (j-1) , it holds that ⃗ s[1], . . . , ⃗ s[j -1] ∈ {j ′ ∈ [d] : ⃗ h[j ′ ] ≥ ⃗ h (j) -r}. As a result, for j ∈ [i + 1 . . k],the number of choices for ⃗ s[j], after determining ⃗ s[1 . . j -1], is C r,j -(j -1).Multiplying the number of choices for each element in ⃗ s ∈ S r,i , we obtain Equation (10).The second key advantage of the partition being considered is that, there is an algorithm for sampling a uniform random sequence from S r,i in O(d) time, as implicitly suggested by the proof for Lemma 4.3. Further details of this implementation are provided in Appendix B.The However, this is unnecessary. We need only to consider the cases for r ∈ [0 . . τ ]. The key observation is that, the probability of sampling an ⃗ s ∈ P D,k decreases exponentially with increasing E(⃗ s). Claim 4.5 (Restatement of Fact 3.6). The probability of sampling an ⃗ s with E(⃗ s) ≥ τ is at most β.To provide further insight, we present a short proof here. Let S ≥τ .EQUATIONwhere ⃗ s * is the k items with the largest scores and E(⃗ s * ) = 0.Given this, if we slightly adjust the loss function of sequences in S ≥τ , their probabilities of being outputted will not be significantly affected. It motivates to consider the truncated loss function:E A (⃗ s) .= min (E(⃗ s), τ ), and an algorithm A which samples an ⃗ s with probability proportional to e -ε•E A (⃗ s)/2 . As inequality (11) still holds if we the E(•) with E A (•), we immediately obtain the following lemma. Lemma 4.6. The probability of A sampling an ⃗ s with E(⃗ s) ≥ τ is at most β.Subset Merging. The most important benefit of truncated loss is that, it allows us to reduce to the number of subsets in the partition S r,i , r∈ [0 . . n], i ∈ [k] from O(nk) to O(τ k). In particular, for each i ∈ [k],as the sequences in the subsets S r,i , r ∈ [τ .. n] has the same truncated loss, it suffices to merge them into oneEQUATIONS ≥τ,i shares a similar formula on its size as Equation ( 9) and can be uniformly sampled efficiently. Lemma 4.7.For each i ∈ [k], we have ln |S ≥τ,i | = i-1 j=1 ln (C τ -1,j -(j -1)) + ln d -C r-1,i + k j=i+1 ln (d -(j -1)). (13) Lemma 4.8. Given the C τ -1,j 's, each ln |S ≥τ,i | can be computed in O(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 B. 
experiment: 
 In this section, we compare our algorithm, referred to as FASTJOINT, with existing state-of-the-art methods on real-world datasets. Our Python implementation is available publicly. 3Datasets. We utilize six publicly available datasets: Games (Steam video games with purchase counts) (Tamber, 2016) , Books (Goodreads books with review counts) (Soumik, 2019) , News (Mashable articles with share counts) (Fernandes 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 1 Baselines. Apart from the JOINT mechanism (Gillenwater et al., 2022) , we consider the following two candidates: the peeling variant of permute-and-flip mechanism (McKenna and Sheldon, 2020) , denoted PNF-PEEL; and the peeling exponential mechanism (Durfee and Rogers, 2019) , denoted CDP-PEEL. We don't compare with other mechanisms, e.g. the Gamma mechanism (Steinke and Ullman, 2016) and the Laplace mechanism (Bhaskar et al., 2010; Qiao et al., 2021) , which are empirically dominated by PNF-PEEL and CDP-PEEL respectively (Gillenwater et al., 2022) .The permute-and-flip is an ε-DP mechanism for top-1 selection. It can be implemented equivalently by adding exponential noise (with privacy budget ε/k) to each entry of ⃗ h and reporting the item with the highest noisy value (Ding et al., 2021) . To report k items, we use the peeling strategy: select one item using the mechanism, remove it from the dataset, and repeat this process k times, resulting in a running time of O(dk).CDP-PEEL: The (ε, δ)-DP peeling exponential mechanism samples k items without replacement, selecting one item at a time using a privacy budget of Õ(ε/ √ k) according to the exponential mechanism (McSherry and Talwar, 2007) . Durfee and Rogers (2019) demonstrate that CDP-PEEL has an equivalent O(d)-time implementation.The code for all competing algorithms was obtained from publicly accessible GitHub repository by Google Research4 , written in Python.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, ε and β. Note that the parameter β (see Theorem 4.1) only affects our algorithm. The (ε, δ)-DP mechanism CDP-PEEL is configured with a δ parameter of 10 -6 , consistent with prior research (Gillenwater et al., 2022) .Error Metrics. We evaluate the quality of a solution ⃗ s using both ℓ ∞ and ℓ 1 errors. The ℓ ∞ error is defined asmax i∈[k] | ⃗ h (i) -⃗ s[i]|, while the ℓ 1 error is given by i∈[k] | ⃗ h (i) -⃗ s[i]|.Parameter Ranges. The parameter ranges tested are as follows:k = 10, 20, . . . , 100, . . . , 200, ε = 1/4, 1/2, 1, 2, 4, β = 2 -6 , 2 -8 , 2 -10 , 2 -12 , 2 -14 .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.All experiments are repeated 200 times. Each figure displays the median running time or ℓ ∞ or ℓ 1 error as the center line, with the shaded region spanning the 25th to the 75th percentiles.Varying k. Figure 1 presents the results for different values k. FASTJOINT consistently outperforms JOINT in terms of execution speed, running 10 to 100 times faster across various datasets. FASTJOINT is slower than CDP-PEEL; the later has theoretical time complexity O(d) 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 et 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 a worst-case time complexity of O(dk 2 ) instead of O(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 PNF-PEEL, which has an O(dk) time complexity. This is because PNF-PEEL has a simple algorithmic structure that can be implemented as k 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-known that vectorized implementations5 gain 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 PNF-PEEL in terms of speed.In terms of solution quality, even with the pruning strategy, FASTJOINT does not experience quality degradation compared to JOINT. It delivers similar performance to JOINT across all datasets and performs particularly well on 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 are included in the appendix, with partial plots provided in Figure 2 ). FASTJOINT consistently outperforms the pure differentially private PNF-PEEL for all values of k and the approximate differentially private CDP-PEEL for at least moderately large k. These results align with the findings of Gillenwater et al. (2022) , who compared JOINT with PNF-PEEL and CDP-PEEL.Varying ε. 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 ℓ 1 error plot (as it exhibits similar trends to the ℓ ∞ plots) with a plot showing the gap between the top-300 scores 6 . The complete plots across all datasets are included in Appendix C. The running time comparison resembles that of the varying-k plots in Figure 1 , with one notable difference: the running time of FASTJOINT exhibits a clear decrease as ε increases. This observation aligns with our theoretical statement about the running time of FASTJOINT, as detailed in Theorem 4.1. In terms of solution quality, FASTJOINT and JOINT perform particularly well on the news dataset and are only slightly better than PNF-PEEL and inferior to 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 an informal but informative explanation for this phenomenon: based on Lemma 4.6, FASTJOINT is unlikely to sample sequences with loss greater than τ . Furthermore, when the distribution of top-k score gaps is highly skewed, there are very few sequences with errors between (0, τ ], and the likelihood of sampling these sequences scales with e -O(ε) as ε varies. In contrast, the peeling-based mechanism needs to divide its privacy budget by k or Õ( √ k) for each round, causing the sampling probability of an error item to scale only with e -O(ε/k) or e -Õ(ε/ √ k) , which is higher than e -O(ε) .Varying β. Due to space constraints, Figure 3 presents results only for different values of β on a medium-sized dataset. Similar plots for other datasets can be found in Appendix C. It is anticipated that JOINT, PNF-PEEL and CDP-PEEL do not exhibit significant performance variation concerning β. However, it is somewhat surprising that FASTJOINT does not neither. This stability can be attributed to the threshold used for pruning, given by τ k) , significantly overshadowing 1/β. Consequently, τ changes only slightly as β varies. This experiment demonstrates the robustness of FASTJOINT's pruning strategy concerning the choice of β. The ℓ 1 /ℓ ∞ plots are padded by 1 to avoid log 0 on the y-axis.= ⌈ 1 ε • ln ( d k • k!/β)⌉. The numerator inside logarithm term, d k • k!, grows as d Θ( 
related work: 
 Comparison with JOINT. We can also explain JOINT (Gillenwater et 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 ⃗ h[1] ≥ • • • ≥ ⃗ h[d],which can be achieved by sorting ⃗ h.For each i ∈ [k] and j ∈ [d], define E i,j . = ⃗ h[i] -⃗ h[j].The partition they consider is equivalent to the one defined as follows:U i,j . =    ⃗ s = (⃗ s[1], . . . , ⃗ s[k]) ∈ P D,k : ⃗ h ⃗ s[ℓ] > ⃗ h[ℓ] -E i,j , ∀ℓ < i ⃗ s[ℓ] = j, ℓ = i ⃗ h ⃗ s[ℓ] ≥ ⃗ h[ℓ] -E i,j , ∀ℓ > i    , ∀i ∈ [k], j ∈ [d].Intuitively, U i,j consists of the length-k sequences, ⃗ s, that satisfy: 1) the i th element in ⃗ s is exactly element j; 2) the first i -1 elements in ⃗ s have losses less than E i,j ; and 3) the last k -i elements in ⃗ s have losses at most E i,j .Therefore, the sequences ⃗ s in U i,j share the same loss, E JOINT ( ⃗ h, ⃗ s) = E i,j (as defined in Equation ( 4)), with the first position reaching this loss being the i th position, where element j appears. Furthermore, sequences in different subsets, U i,j and U i ′ ,j ′ , can share the same loss, as it is possible that E i,j = E i ′ ,j ′ . There are dk subsets in this partition, resulting in a running time of Õ(dk) for their implementation (Gillenwater et al., 2022) .Applying the pruning technique to this partition can not reduce the number of subsets to o(dk). Let τ be as defined in Theorem 4.1. For each i ∈ [k], we aim to find the first j such that ⃗ h[j] ≤ ⃗ h (i) -τ . Denote this value by σ(i) . = min{j ∈ [d] : ⃗ h[j] ≤ ⃗ h (i) -τ }.Following the spirit of our pruning technique, we would like to merge the trailing subsets U i,σ(i) , . . . , U i,d into a single subset U i,σ(i) . = j≥σ(i) U i,j to reduce the number of subsets. However, it is easy to find counterexamples where Ω(d) items are equal to ⃗ h (i) for all i ∈ [k]. For example, consider the case where ⃗ h[1] = ⃗ h[2] = • • • = ⃗ h[d] = c,for some constant c. In such scenarios, we still have σ(i) ∈ Ω(d), and therefore, in the worst case, the number of subsets remains i∈[k] σ(i) ∈ Ω(dk).Truncated Loss. 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-based approach: it samples k items without replacement, selecting one item at a time using the exponential mechanism with truncated scores. This method is employed because, in their setting, obtaining the scores of the input histogram ⃗ h is expensive, leading them to treat lower-scoring items uniformly by assigning them a small, identical score. In contrast, when all scores of ⃗ h are known, iteratively applying the exponential mechanism to select the top-k items has an equivalent linear time implementation (Durfee and Rogers, 2019) (the CDP-PEEL algorithm in Section 5). Therefore, truncating the scores of ⃗ h is unnecessary in this case.Adaptive Private k Selection. As the experiments show, the performance of JOINT and FASTJOINT depends on gap size-they 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 i th and (i + 1) th largest elements. This is followed by testing whether the gap (using techniques like propose-test-release) between the i th and (i + 1) th largest elements is sufficiently large, allowing the top-i items to be returned without additional noise. This approach benefits by adding no noise in 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-i 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, FASTJOINT 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 (2017) demonstrate that, for approximate private algorithms, existing methods (Durfee and Rogers, 2019; Qiao et al., 2021) , including CDP-PEEL (Durfee and Rogers, 2019) as compared in Section 5, achieve theoretically asymptotically optimal privacy-utility trade-offs.Proof for Fact 3.5. The proof has been implicitly suggested in our comparison with JOINT in Section 6. We reiterate it here.We explain JOINT (Gillenwater et 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 ⃗ h[1] ≥ • • • ≥ ⃗ h[d],which can be achieved by sorting ⃗ h.For each i ∈ [k] and j ∈ [d], define E i,j . = ⃗ h[i] -⃗ h[j].The partition they consider is equivalent to the one defined as follows:U i,j . =    ⃗ s = (⃗ s[1], . . . , ⃗ s[k]) ∈ P D,k : ⃗ h ⃗ s[ℓ] > ⃗ h[ℓ] -E i,j , ∀ℓ < i ⃗ s[ℓ] = j, ℓ = i ⃗ h ⃗ s[ℓ] ≥ ⃗ h[ℓ] -E i,j , ∀ℓ > i    , ∀i ∈ [k], j ∈ [d].Intuitively, U i,j consists of the length-k sequences, ⃗ s, that satisfy: 1) the i th element in ⃗ s is exactly element j; 2) the first i -1 elements in ⃗ s have losses less than E i,j ; and 3) the last k -i elements in ⃗ s have losses at most E i,j .Therefore, the sequences ⃗ s in U i,j share the same loss, E JOINT ( ⃗ h, ⃗ s) = E i,j (as defined in Equation ( 4)), with the first position reaching this loss being the i th position, where element j appears. Furthermore, sequences in different subsets, U i,j and U i ′ ,j ′ , can share the same loss, as it is possible thatE i,j = E i ′ ,j ′ .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 i,j can be achieved similarly (though not identically) to the approach used in Algorithm 2 for sampling a sequence from S r,i . This process can be completed in O(d) time.For the Subset Sampling step, similar to the algorithm in Section 4.1 and using Fact 3.4, sampling a subset U i,j with probability proportional to |U i,j | • exp (-ε • E i,j /2), can be achieved by computing the maximum ofX i,j + ln |U i,j | • exp (-ε • E i,j /2) : (i, j) ∈ [k] × [d] ,where X i,j ∼ Gumbel (1). The main task is to efficiently compute ln |U i,j |.For each i ∈ [k], j ∈ [d], ℓ ∈ [k], we define t i,j,> [ℓ] . = j ′ ∈ [d] : ⃗ h[j ′ ] > ⃗ h[ℓ] -E i,j , and t i,j,≥ [ℓ] . = j ′ ∈ [d] : ⃗ h[j ′ ] ≥ ⃗ h[ℓ] -E i,j .It can be shown thatln |U i,j | = ℓ∈[i-1] ln t i,j,> [ℓ] -(ℓ -1) + ℓ∈[i+1 . . k] ln t i,j,≥ [ℓ] -(ℓ -1) . Furthermore, if we define ti,j [ℓ] . = j ′ ∈ [d] : ⃗ h[j ′ ] ≥ ⃗ h[ℓ] -E i,j - i -ℓ 2k - j -j ′ 2dk , we observe that i-ℓ 2k -j-j ′ 2dk < 1. When ℓ < i, i-ℓ 2k -j-j ′ 2dk ≥ 1 2k -d-1 2dk > 0, so ti,j [ℓ] = t i,j,> [ℓ]. On the other hand, when ℓ > i, i-ℓ 2k -j-j ′ 2dk ≤ -1 2k -d-1 2dk < 0, so ti,j [ℓ] = t i,j,≥ [ℓ]. Therefore, it follows that ln |U i,j | = ℓ̸ =i ln ti,j [ℓ] -(ℓ -1) .It remains to demonstrate an efficient method for computing ti,j . First, we sort the (i, j)∈ [k] × [d]pairs in increasing order based on E i,j + i 2k -j 2dk . For a fixed i, the values E i,j for j ∈ [d] are already in increasing order, so a sorted sequence of E i,j + i 2k -j 2dk for j ∈ [d] can be obtained in O(d) time. We then merge k sorted sequences in O(dk log k) time using k-way merging.If ( î, ĵ) appears immediately after (i, j) in the sorted order, then ln |U î, ĵ | can be derived from ln |U i,j | in O(1) time. Specifically, we claim thattî , ĵ [ℓ] = ti,j [ℓ], if ℓ ̸ = î, ti,j [ℓ] + 1, if ℓ = î.For the first case, assume for contradiction that there exists some ℓ ̸ = î such that tî , ĵ [ℓ] > ti,j [ℓ]. Consequently, there exists j ′ such thatEQUATION)which implies thatEQUATION)Since the values of E i,j + i 2k -j 2dk are distinct, it follows thatEQUATION)which contradicts the assumption that ( î, ĵ) appears immediately after (i, j) in the sorted order.For the second case (ℓ = î), it is clear that tî, ĵ [ℓ] ≥ ti,j [ℓ]. Additionally, observe that ⃗ h[ î] -E i,j - i - î 2k - j - ĵ 2dk > ⃗ h[ ĵ] ≥ ⃗ h[ î] -E î, ĵ - î - î 2k - ĵ - ĵ 2dk implying that tî , ĵ [ℓ] ≥ ti,j [ℓ] + 1. Finally, we show that it is impossible for tî , ĵ [ℓ] to exceed ti,j [ℓ] + 1.If it did, then, using reasoning similar to Inequalities ( 14), ( 15), and ( 16), we could conclude that there exists some ( î, j ′ ) that appears between (i, j) and ( î, ĵ), which leads to a contradiction.Proof for Lemma 4.7. The proof is under the same spirit as the proof of Lemma 4.3.|S ≥τ,i | = i-1 j=1 (C τ -1,j -(j -1)) • d -C τ -1,i • k j=i+1 (d -(j -1)). (17) Recall Equation (12) that S ≥τ,i . = ∪ r∈[τ . . n] S r,i = ⃗ s = (⃗ s[1], . . . , ⃗ s[k]) ∈ P D,k : ⃗ h ⃗ s[j] > ⃗ h (j) -τ, ∀j < i ⃗ h ⃗ s[j] ≤ ⃗ h (j) -τ, j = i .Assume we want to select a sequence ⃗ s ∈ S ≥τ,i . Since⃗ s[1] ∈ {j ′ ∈ [d] : ⃗ h[j ′ ] > ⃗ h (1) -τ }, the number of possible choices for ⃗ s[1] is |{j ′ ∈ [d] : ⃗ h[j ′ ] > ⃗ h (1) -τ }| = |{j ′ ∈ [d] : ⃗ h[j ′ ] ≥ ⃗ h (1) -(τ -1)}| = C τ -1,1 . The first equality holds because the ⃗ h[j ′ ] values are integers. Since ⃗ h (ℓ) is non-decreasing, for each ℓ < j < i, ⃗ h[⃗ s[ℓ]] > ⃗ h (ℓ) -τ ≥ ⃗ h (j) -τ , therefore ⃗ h (ℓ) ∈ {j ′ ∈ [d] : ⃗ h[j ′ ] > ⃗ h (j) -τ }. After determining ⃗ s[1 . . j -1], ⃗ s[j] must be chosen from {j ′ ∈ [d] : ⃗ h[j ′ ] > ⃗ h (j) -τ } \ {⃗ s[ℓ] : ℓ < j}, so it has |{j ′ ∈ [d] : ⃗ h[j ′ ] > ⃗ h (j) -τ }| -(j -1) = C τ -1,j -(j -1) choices.Now we consider the number of choices for ⃗ s[i]. Since ⃗ s[1], . . . , ⃗ s[i -1] ∈ {j ′ ∈ [d] : ⃗ h[j ′ ] > ⃗ h (i) -τ }, they do not appear in {j ′ ∈ [d] : ⃗ h[j ′ ] ≤ ⃗ h (i) -τ }. The number of choices for ⃗ s[i] is exactly |{j ′ ∈ [d] : ⃗ h[j ′ ] ≤ ⃗ h (i) -τ }| = d -C τ -1,i . For j ∈ [i + 1 . . k], the number of choices for ⃗ s[j], after determining ⃗ s[1 . . j -1], is d -(j -1).Multiplying the number of choices for each element in ⃗ s ∈ S ≥τ,i , we get|S r,i | = i-1 j=1 (C τ -1,j -(j -1)) • d -C τ -1,i • k j=i+1 (d -(j -1)).In this section, we discuss how to implement the Subset Sampling and Sequence Sampling steps, according to the partition {S r,i : r ∈[0 . . τ -1], i ∈ [k]} ∪ {S ≥τ,i : i ∈ [k]} induced by the loss E A .The algorithm is in Algorithm 1.Computing the C r,j . Let f ⃗ h : N → 2 N be the function given by f⃗ h [t] . = {i ∈ D : ⃗ h[i]= t}, ∀t ∈ N. By using standard hash map, f ⃗ h can be computed with O(d) time and space. Based on the definition of the C r,j 's and that ⃗ h consists of only integer scores, the following recursion holds,EQUATIONTherefore, C r,j 's can be computed in O(d + τ k) time.Computing ln |S r,i | and ln |S ≥τ,i |. To simplify the notation, we apply the following definitions.Definition B.1.EQUATIONFor each r ∈ [0 . . τ ] and each i ∈ [1 . . k], define the prefix and the suffix sums byEQUATIONFor convenience, we assume ⃗ σ[•, 0] = ⃗ σ[•, k + 1] = 0. Combining Equation ( 9) and ( 13), we haveEQUATIONA corner case is r = 0. By definition, | S0,i | = 0 unless i = 0. We can set C-1,0 = 0 and the equation still holds.Algorithm 1 Subset SamplingInput: Histogram ⃗ h; Privacy Parameter ε 1: Compute f ⃗ h : N → 2 N s.t. f ⃗ h [t] . = {i ∈ D : ⃗ h[i] = t}, ∀t ∈ N.2: Compute the Cr,j 's according to Equation ( 18) and Equation (20) 3: Compute the ⃗ σ's and ⃗ σ's according to Equation (21) 4: Compute the ln | Sr,i |'s according to Equation ( 22)5: Sample (r, i) ← arg max X r,i + ln |S r,i | • exp (-ε • r/2) , where X r,i ∼ Gumbel (1) 6: return (r, i)The algorithm for sequence sampling is Algorithm 2. It follows from the counting argument in Lemma 9 when r < τ and Lemma 13 when r = τ . Lemma B.2. Algorithm 2 can be implemented in O(d) time.Input: (r, i) Ensure: ⃗ s r ←-Sr,i 1: Let ⃗ s ← ∅ be an empty length-k array 2: for j ← 1 to i -1 do3: Sample ⃗ s[j] r ←-{ℓ ∈ D : ⃗ h[ℓ] > ⃗ h (j) -r} \ {⃗ s[1], . . . , ⃗ s[j -1]} 4: Sample an ⃗ s[j] r ←- {ℓ ∈ D : ⃗ h[ℓ] = ⃗ h (i) -r}, if r < τ {ℓ ∈ D : ⃗ h[ℓ] ≤ ⃗ h (i) -τ }, if r = τ 5: for j ← i + 1 to k do 6: Sample an ⃗ s[j] r ←- {ℓ ∈ D : ⃗ h[ℓ] ≥ ⃗ h (j) -r} \ {⃗ s[1], . . . , ⃗ s[j -1]} , if r < τ D \ {⃗ s[1], . . . , ⃗ s[j -1]} , if r = τ 7: return ⃗ sProof of Lemma B.2. We discuss different sections of pseudo-codes of Algorithm 2, start by the easy ones.Case I : Algorithm 2, line 4. Clearly, this can be implemented in O(d) time.Case II: Algorithm 2, line 5-6, when r = τ . After the first i entries of ⃗ s are determined, we can create an dynamic array, denoted ⃗ a, consisting of elements D \ {⃗ s[1], . . . , ⃗ s[i]}. This takes O(d) time. Sampling and removing an item from ⃗ a can be done in O(1) time via standard technique, as described in Algorithm 3 (the AS(•) procedure).Case III: Algorithm 2, line 2-3. This section can be implemented in O(d + (k + τ ) log(k + τ )) time, as described in Algorithm 3 (the efficient sequence sampler procedure). It first computes a functionf ⃗ h : N → 2 N , s.t., f ⃗ h (t) . = {i ∈ D : ⃗ h[i] = t}, ∀t ∈ N.By using standard hash map, f ⃗ h can be computed with O(d) time and space. Then it finds the setI . = {t ∈ N : f ⃗ h (t) ̸ = ∅ ∧ t > ⃗ h (k)-τ }, and store elements in I as an array. It can be computed in O(d) time. Since an item in I must equal one of the values of ⃗ h (1) , . . . , ⃗ h (k) , ⃗ h (k) -1, . . . , ⃗ h (k) -τ + 1, it is easy to see that |I| ≤ k + τ . So sorting the items in I in decreasing order takes O((k + τ ) log(k + τ )) time. Then the algorithm create an empty dynamic array ⃗ a, and a variable POS = 0. For each j ∈ [i -1], before the sampling step (Algorithm 3, line 18), we claim the following holds:• POS = arg max z I[z] > ⃗ h (j) -r • ⃗ a = {ℓ ∈ D : ⃗ h[ℓ] > ⃗ h (j) -r} \ {⃗ s[1], . . . , ⃗ s[j -1]}This is true for j = 1. Now, assume this is true for the j and consider the case for j + 1. After the sampling step (Algorithm 3, line 18) in the jth iteration, we have POS = arg maxz I[z] > ⃗ h (j) -r and ⃗ a = {ℓ ∈ D : ⃗ h[ℓ] > ⃗ h (j) -r} \ {⃗ s[1], . . . , ⃗ s[j]}. At the (j + 1)-th iteration, the inner loop (Algorithm 3, lines 15-17) increases POS from z 1 . = arg max z I[z] > ⃗ h (j) -r) to z 2 . = arg max z I[z] > ⃗ h (j+1) -r, and expand ⃗ a correspondingly. Since {I[z 1 ], . . . , I[z 2 ]} contains all t ∈ [ ⃗ h (j+1) -r + 1, ⃗ h (j) -r] s.t., f ⃗ h t ̸ = ∅, after this, ⃗ a becomes ⃗ a = ℓ ∈ D : ⃗ h[ℓ] > ⃗ h (j) -r \ {⃗ s[1], . . . , ⃗ s[j]}    ⃗ h (j) -r t= ⃗ h (j+1) -r+1 f ⃗ h t    = ℓ ∈ D : ⃗ h[ℓ] > ⃗ h (j) -r \ {⃗ s[1], . . . , ⃗ s[j]} ℓ ∈ [d] : ⃗ h (j) -r ≥ ⃗ h[ℓ] > ⃗ h (j+1) -r = ℓ ∈ D : ⃗ h[ℓ] > ⃗ h (j+1) -r \ {⃗ s[1], . . . , ⃗ s[j]}Therefore the invaraints are maintained.Case IV: Algorithm 2, line 5-6, when r < τ . Observe that {ℓ ∈ D : return ans. ⃗ a ← an empty dynamic array 13:⃗ h[ℓ] ≥ ⃗ h (j) -r} = {ℓ ∈ D : ⃗ h[ℓ] > ⃗ h (j) -8: Procedure EFFICIENT SEQUENCE SAMPLER Input: Histogram ⃗ h; Parameter i ∈ [k]. 9: Compute the function f ⃗ h : N → 2 N , s.t., f ⃗ h (t) . = {ℓ ∈ D : ⃗ h[ℓ] = t}, ∀t ∈ N 10: Compute I ← {t ∈ N : f ⃗ h (t) ̸ = ∅ ∧ t > ⃗ h (k) -τ }POS ← 0 14:for j ← 1 to i -1 do 15: while POS < length of I ∧ I[POS + 1] > ⃗ h (j) -r do 16: Add the items f ⃗ h I[POS + 1] to the back of ⃗ a 17: POS ← POS + 1 18: ⃗ s[j] ← AS(⃗ a) 19: return ⃗ s[1], . . . , ⃗ s[i -1].Though FASTJOINT is not implemented yet fully vectorized, we discuss its potential here. = {i ∈ D : ⃗ h[i] = t} for each unique value t in ⃗ h. This computation could be vectorized using an appropriate library.The second O(d) component in Sequence Sampling can be eliminated with a careful implementation. Recall that in Algorithm 2, a crucial step is to sample elements uniformly at random from the setEQUATIONfor a possible value of r ∈ {1, 2, . . . , τ }. Sampling from the set {ℓ ∈ D :⃗ h[ℓ] ≥ ⃗ h (j) -r} \ {⃗ s[1], . . . , ⃗ s[j -1]} can be handled similarly.To achieve this, we construct an array of at most k + τ buckets (the cost of constructing this array is covered by the initial O(d) time cost):f ⃗ h [ ⃗ h (1) ], f ⃗ h [ ⃗ h (2) ], . . . , f ⃗ h [ ⃗ h (k) ], f ⃗ h [ ⃗ h (k) -1], . . . , f ⃗ h [ ⃗ h (k) -τ ] .Assume that each f ⃗ h [t] in this array is itself managed by a dynamic array. Sampling from ( 23) is then equivalent to sampling uniformly from a prefix of buckets without replacement.The sampling process involves first selecting a bucket with probability proportional to its size, then drawing an element uniformly at random from that bucket. After sampling, the chosen element is removed from the bucket, which can be managed efficiently using a dynamic array. This approach removes the dependency on d in the sampling step. 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 be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: Experiment environment is reported in the paper.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: We don'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 circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 privacy-preserving data analysis and is of theoretical nature. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification:Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses 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 not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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.https://github.com/wuhao-wu-jiang/Differentially-Private-Top-k-Selectionhttps://github.com/google-research/google-research/tree/master/dp_topkIn Appendix B, we discuss in more detail the possibility of implementing FASTJOINT with vertoziation.The k used for the varying ε experiments is 100; here we plot the gap for the top-300 scores 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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).
strength_weakness: strength_weakness: 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.
questions: 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: limitations: N/A
paper_summary: paper_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). 

In 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. 

Their 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.
strength_weakness: strength_weakness: The paper doesn't have any weaknesses that I can pinpoint.
questions: questions: I had a couple of questions about the experiments:

1) 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.

2) For the food dataset, the sudden drop in variance of the error of FastJoint close to k=100 seems very strange- what happened here?

3) For small datasets, is there any hope to utilize the benefits of vectorization for FastJoint as well? Some comment may be nice.
limitations: limitations: Yes.
paper_summary: paper_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).

The 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)$.

In 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.
strength_weakness: strength_weakness: - 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?
- 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.
- Minor: Order the references alphabetically.
questions: questions: - Is the $O(d + nk)$ time version of the algorithm before pruning already new in this work?
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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).

- 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?
questions: questions: Could you answer these questions ( I am ready to reconsider my score ):

When 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?

Minor comments:

- p.1, line 31: "the its"
- p.3, line 96: "lose function"
- p.3, Equation 4: Please add some definition/explanation of $s$
- p.5, line 177: "is decreases"
limitations: limitations: Yes.

Comments: title: Response to rebuttal
comment: Thank you for the suggestion and for appreciating our work. We will include the relevant discussions in the final version.
Thanks for addressing my suggestions.
Re 3, I was referring to the discussion starting line 268 of the paper regarding PNF peel being faster than FastJoint on small datasets (where I'm assuming $d$ is smaller) because of vectorization. It's good to know however that the $O(d)$ part can be vectorized.

Re 1, I was referencing the time plot (not the error plot). 

Re 2, I was referring to the sudden drop in variance of error for the food dataset around k=90 (see some of the area shaded only Orange) . FastJoint's error is indeed gap dependent, but should the same phenomenon not apply then to Joint as well? Additionally, this is only around k=90 but after that the variance goes up again, so it seems curious.
Thank you for the replies! This makes it clearer and I will raise my score.

> We will incorporate relevant discussions to provide a broader perspective and better position our paper.

Please do so! I think this would be very valuable, based on a quick glance it seems that the original JOINT paper is not making these connections.
We delve into these challenges in more detail and demonstrate how the algorithms studied in our paper can be leveraged to address them.

- **First Issue: Unordered Output:** This occurs when PTR determines that the gap between the $k^{(th)}$ and $(k + 1)^{(th)}$ largest elements is sufficiently large, resulting in the top-$k$ items being returned as an unordered set. To resolve this, one can use Joint-style algorithms, which are effective when there are still large gaps between the $i^{(th)}$ and $(i + 1)^{(th)}$ largest elements for $i \leq k$.

- **Second Issue: No Output:** This happens when PTR concludes that the gap between the $k^{(th)}$ and $(k + 1)^{(th)}$ largest elements is not significant enough. We can consider two potential solutions:

  1. **Invoke a Private Top-$k$ Selection Algorithm:** Use one of the private top-$k$ selection algorithms discussed in the paper. JOINT-style algorithms are particularly suitable if there are still large gaps between the $i^{(th)}$ and $(i + 1)^{(th)}$ largest elements for $i = 1, 2, ..., k - 1$. In this case, JOINT can reliably identify the first $k - 1$ largest items, allocating the privacy budget  primarily on the last item. In contrast, CDP-Peel would need to split the privacy budget across all $k$ items.

  2. **Use Report Noisy Max:** Use the Report-Noisy-Max technique to approximately identify the index $i$ that maximizes the gap between the $i^{(th)}$ and $(i + 1)^{(th)}$ largest elements. After identifying this index, test whether the gap is sufficient to determine the top-$i$ set. However, if $i < k$ —- which occurs when the gap between the $i^{(th)}$ and $(i + 1)^{(th)}$ largest elements is significantly larger than the gap between the $k^{(th)}$ and $(k + 1)^{(th)}$ —- JOINT-style algorithms can be employed to identify the remaining top-$(k - i)$ items, assuming there are still large gaps between their counts.

        This approach draws inspiration from Zhu and Wang ("Adaptive private-k-selection with adaptive k and application to multi-label pate", 2022), where they considered using Report-Noisy-Max alongside CDP-Peel, and focused on returning the top-$k$ items as an unordered set.
Thank you for the insightful question. 

When tackling the version of the top-$k$ selection problem where items must be returned as an ordered sequence and $k$ is fixed, the Propose-Test-Release (PTR) style approach encounters two key challenges:

1. **Unordered Output:** PTR may only return the top-$k$ items as an unordered set because two neighboring datasets can have the same collection of top-$k$ elements in a different order. In contrast, the algorithms we compare in the paper return them as an ordered sequence.

2. **No Output:** PTR might not return any meaningful result at all (it could return a $\bot$).

To overcome these challenges, it is essential to use the algorithms discussed in the paper—such as FastJOINT, JOINT, and CDP-Peel—as fundamental tools. 
Therefore, studying and comparing the relative performance of these primitives independently is still valuable.
We will incorporate relevant discussions to provide a broader perspective and better position our paper.
Thank you for the replies! I would still have a question: in case you have a large gap between $k$th and $(k+1)$th largest elements, wouldn't it make sense to compare this method to some Propose-Test-Release type of algorithm, where you first test whether there is a large gap between the scores? If you know that there is a large gap, you can release the top-$k$ elements without additional privacy cost. And that would also probably have the complexity $\widetilde{O}(d)$. What would be the benefits of this JOINT approach then?
Thanks for addressing my question. I will raise my score.