@inproceedings{
wu2024faster,
title={Faster Differentially Private Top-\$k\$ Selection: A Joint Exponential Mechanism with Pruning},
author={Hao WU and Hanwen Zhang},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=QyxE3W9Yni}
}
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 Hanwen Zhang