# Practical Differentially Private Top-k Selection with Pay-what-you-get Composition

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 May 2019.

## Built on by (most cited first, 30 of 39)

- [DP-OPT: Make Large Language Model Your Privacy-Preserving Prompt Engineer](https://mlsanity.com/paper/2312.03724/) (2023)
- [Differentially Private Query Release Through Adaptive Projection](https://mlsanity.com/paper/2103.06641/) (2021)
- [Privacy-Preserving In-Context Learning for Large Language Models](https://mlsanity.com/paper/2305.01639/) (2023)
- [Covariance-Aware Private Mean Estimation Without Private Covariance Estimation](https://mlsanity.com/paper/2106.13329/) (2021)
- [Privacy-Preserving Retrieval-Augmented Generation with Differential Privacy](https://mlsanity.com/paper/2412.04697/) (2024)
- [Private Synthetic Data for Multitask Learning and Marginal Queries](https://mlsanity.com/paper/2209.07400/) (2022)
- [Private prediction for large-scale synthetic text generation](https://mlsanity.com/paper/2407.12108/) (2024)
- [Generating Private Synthetic Data with Genetic Algorithms](https://mlsanity.com/paper/2306.03257/) (2023)
- [Wide Network Learning with Differential Privacy](https://mlsanity.com/paper/2103.01294/) (2021)
- [Oneshot Differentially Private Top-k Selection](https://mlsanity.com/paper/2105.08233/) (2021)
- [Open LLMs are Necessary for Current Private Adaptations and Outperform their Closed Alternatives](https://mlsanity.com/paper/2411.05818/) (2024)
- [DPAR: Decoupled Graph Neural Networks with Node-Level Differential Privacy](https://mlsanity.com/paper/2210.04442/) (2022)
- [Adaptive Private-K-Selection with Adaptive K and Application to Multi-label PATE](https://mlsanity.com/paper/2203.16100/) (2022)
- [Safeguarding Privacy of Retrieval Data against Membership Inference Attacks: Is This Query Too Close to Home?](https://mlsanity.com/paper/2505.22061/) (2025)
- [Quantifying and Defending against Privacy Threats on Federated Knowledge Graph Embedding](https://mlsanity.com/paper/2304.02932/) (2023)
- [Distribution-Invariant Differential Privacy](https://mlsanity.com/paper/2111.05791/) (2021)
- [Unbounded Differentially Private Quantile and Maximum Estimation](https://mlsanity.com/paper/2305.01177/) (2023)
- [Better Private Linear Regression Through Better Private Feature Selection](https://mlsanity.com/paper/2306.00920/) (2023)
- [Hot PATE: Private Aggregation of Distributions for Diverse Task](https://mlsanity.com/paper/2312.02132/) (2023)
- [Private-RAG: Answering Multiple Queries with LLMs while Keeping Your Data Private](https://mlsanity.com/paper/2511.07637/) (2025)
- [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)
- [Feature Selection from Differentially Private Correlations](https://mlsanity.com/paper/2408.10862/) (2024)
- [The Correlated Gaussian Sparse Histogram Mechanism](https://mlsanity.com/paper/2412.10357/) (2024)
- [Differentially Private Retrieval-Augmented Generation](https://mlsanity.com/paper/2602.14374/) (2026)
- [FedST: Secure Federated Shapelet Transformation for Time Series Classification](https://mlsanity.com/paper/2302.10631/) (2023)
- [On the Computational Complexity of Private High-dimensional Model Selection](https://mlsanity.com/paper/2310.07852/) (2023)
- [Unleash the Power of Ellipsis: Accuracy-enhanced Sparse Vector Technique with Exponential Noise](https://mlsanity.com/paper/2407.20068/) (2024)
- [Differentially Private Multimodal In-Context Learning](https://mlsanity.com/paper/2603.04894/) (2026)
- [On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCA](https://mlsanity.com/paper/2606.21951/) (2026)

## Abstract (arXiv)

We study the problem of top-k selection over a large domain universe subject to user-level differential privacy. Typically, the exponential mechanism or report noisy max are the algorithms used to solve this problem. However, these algorithms require querying the database for the count of each domain element. We focus on the setting where the data domain is unknown, which is different than the setting of frequent itemsets where an apriori type algorithm can help prune the space of domain elements to query. We design algorithms that ensures (approximate) (ε,δ>0)-differential privacy and only needs access to the true top-bark elements from the data for any chosen bark ≥ k. This is a highly desirable feature for making differential privacy practical, since the algorithms require no knowledge of the domain. We consider both the setting where a user's data can modify an arbitrary number of counts by at most 1, i.e. unrestricted sensitivity, and the setting where a user's data can modify at most some small, fixed number of counts by at most 1, i.e. restricted sensitivity. Additionally, we provide a pay-what-you-get privacy composition bound for our algorithms. That is, our algorithms might return fewer than k elements when the top-k elements are queried, but the overall privacy budget only decreases by the size of the outcome set.