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

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.

Strengths

- The paper is very well written, in particular the motivation and introduction to the topic - 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). - 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

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"

Rating

6

Confidence

3

Soundness

4

Presentation

3

Contribution

2

Limitations

Yes.

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.

Strengths

- The problem is well-motivated and important within differential privacy. - The proposed change to prior work is simple and yields a significant benefit in the theoretical bounds. - 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? - 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

- Is the $O(d + nk)$ time version of the algorithm before pruning already new in this work?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A

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.

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

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.

Rating

7

Confidence

4

Soundness

4

Presentation

4

Contribution

3

Limitations

Yes.

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

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.

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.

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A