# A Joint Exponential Mechanism For Differentially Private Top-k

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jan 2022.

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

- [Privacy-Preserving In-Context Learning for Large Language Models](https://mlsanity.com/paper/2305.01639/) (2023)
- [Privacy Preserving Prompt Engineering: A Survey](https://mlsanity.com/paper/2404.06001/) (2024)
- [Open LLMs are Necessary for Current Private Adaptations and Outperform their Closed Alternatives](https://mlsanity.com/paper/2411.05818/) (2024)
- [Adaptive Private-K-Selection with Adaptive K and Application to Multi-label PATE](https://mlsanity.com/paper/2203.16100/) (2022)
- [Better Private Linear Regression Through Better Private Feature Selection](https://mlsanity.com/paper/2306.00920/) (2023)
- [Differentially Private Top-k Selection via Canonical Lipschitz Mechanism](https://mlsanity.com/paper/2201.13376/) (2022)
- [Differentially Private Prototypes for Imbalanced Transfer Learning](https://mlsanity.com/paper/2406.08039/) (2024)
- [DP-GTR: Differentially Private Prompt Protection via Group Text Rewriting](https://mlsanity.com/paper/2503.04990/) (2025)
- [Differentially Private In-Context Learning with Nearest Neighbor Search](https://mlsanity.com/paper/2511.04332/) (2025)
- [CHRONOS: Temporally-Aware Multi-Agent Coordination for Evolving Data Marketplaces](https://mlsanity.com/paper/2605.23887/) (2026)

## Abstract (arXiv)

We present a differentially private algorithm for releasing the sequence of k elements with the highest counts from a data domain of d elements. The algorithm is a "joint" instance of the exponential mechanism, and its output space consists of all O(dk) length-k sequences. Our main contribution is a method to sample this exponential mechanism in time O(dklog(k) + dlog(d)) and space O(dk). Experiments show that this approach outperforms existing pure differential privacy methods and improves upon even approximate differential privacy methods for moderate k.