# Oneshot Differentially Private Top-k Selection

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 37 references that are in the map.
- First posted on arXiv 18 May 2021.

## Builds on (most cited first, 14 of 14)

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [Concentrated Differential Privacy](https://mlsanity.com/paper/1603.01887/) (2016)
- [Deep Learning with Gaussian Differential Privacy](https://mlsanity.com/paper/1911.11607/) (2019)
- [Spectral Method and Regularized MLE Are Both Optimal for Top-K Ranking](https://mlsanity.com/paper/1707.09971/) (2017)
- [Practical Differentially Private Top-k Selection with Pay-what-you-get Composition](https://mlsanity.com/paper/1905.04273/) (2019)
- [Tight Lower Bounds for Differentially Private Selection](https://mlsanity.com/paper/1704.03024/) (2017)
- [Differentially Private False Discovery Rate Control](https://mlsanity.com/paper/1807.04209/) (2018)
- [The Price of Selection in Differential Privacy](https://mlsanity.com/paper/1702.02970/) (2017)
- [Private False Discovery Rate Control](https://mlsanity.com/paper/1511.03803/) (2015)
- [Beyond Worst-Case Analysis](https://mlsanity.com/paper/1806.09817/) (2018)
- [Optimal Differential Privacy Composition for Exponential Mechanisms and the Cost of Adaptivity](https://mlsanity.com/paper/1909.13830/) (2019)

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

- [Zeroth-Order Optimization Meets Human Feedback: Provable Learning via Ranking Oracles](https://mlsanity.com/paper/2303.03751/) (2023)
- [A Fast Algorithm for Adaptive Private Mean Estimation](https://mlsanity.com/paper/2301.07078/) (2023)
- [Adaptive Private-K-Selection with Adaptive K and Application to Multi-label PATE](https://mlsanity.com/paper/2203.16100/) (2022)
- [On Noisy Evaluation in Federated Hyperparameter Tuning](https://mlsanity.com/paper/2212.08930/) (2022)
- [Hot PATE: Private Aggregation of Distributions for Diverse Task](https://mlsanity.com/paper/2312.02132/) (2023)
- [Differentially Private Top-k Selection via Canonical Lipschitz Mechanism](https://mlsanity.com/paper/2201.13376/) (2022)
- [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)
- [Majority Vote for Distributed Differentially Private Sign Selection](https://mlsanity.com/paper/2209.04419/) (2022)
- [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)
- [Improved Regret in Stochastic Decision-Theoretic Online Learning under Differential Privacy](https://mlsanity.com/paper/2502.10997/) (2025)
- [Optimal Differentially Private Ranking from Pairwise Comparisons](https://mlsanity.com/paper/2507.09388/) (2025)
- [On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCA](https://mlsanity.com/paper/2606.21951/) (2026)
- [Optimal Bounds for Private Minimum Spanning Trees via Input Perturbation](https://mlsanity.com/paper/2412.10130/) (2024)
- [Improved Private Sparse Covariance Estimation with Multiscale Threshold Tests](https://mlsanity.com/paper/2609.22783/) (2026)

## Abstract (arXiv)

Being able to efficiently and accurately select the top-k elements with differential privacy is an integral component of various private data analysis tasks. In this paper, we present the oneshot Laplace mechanism, which generalizes the well-known Report Noisy Max mechanism to reporting noisy top-k elements. We show that the oneshot Laplace mechanism with a noise level of widetildeO(√k/eps) is approximately differentially private. Compared to the previous peeling approach of running Report Noisy Max k times, the oneshot Laplace mechanism only adds noises and computes the top k elements once, hence much more efficient for large k. In addition, our proof of privacy relies on a novel coupling technique that bypasses the use of composition theorems. Finally, we present a novel application of efficient top-k selection in the classical problem of ranking from pairwise comparisons.