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

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.

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.

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.

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

We thank all the reviewers for their consideration of our manuscript and their constructive feedback.

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.