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

arXiv: https://arxiv.org/abs/2411.09552 · HTML: https://mlsanity.com/paper/2411.09552/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Nov 2024.

## Built on by (most cited first, 2 of 2)

- [The Correlated Gaussian Sparse Histogram Mechanism](https://mlsanity.com/paper/2412.10357/) (2024)
- [Differentially Private In-Context Learning with Nearest Neighbor Search](https://mlsanity.com/paper/2511.04332/) (2025)

## Abstract (arXiv)

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. (ICML '22) employs a direct sampling approach from the vast collection of d,Theta(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 tildeO(dk). In this paper, we present an improved algorithm with time and space complexity O(d + k2 / ε · ln d), where ε denotes the privacy parameter. Experimental results show that our algorithm runs orders of magnitude faster than their approach, while achieving similar empirical accuracy.