mlsanityData to 7 Oct 2026

Oneshot Differentially Private Top-k Selection

arXiv 2105.08233 ↗First posted 18 May 2021cs.LG cs.CR stat.MLcited by 16

Not on the map. Why?

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.

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

Builds on

14 of 37 references.

References · 14

  1. 2016Deep Learning with Differential Privacycited by 2,682
  2. 2017Renyi Differential Privacycited by 643
  3. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 339
  4. 2013The Composition Theorem for Differential Privacycited by 290
  5. 2016Concentrated Differential Privacycited by 139
  6. 2019Deep Learning with Gaussian Differential Privacycited by 112
  7. 2017Spectral Method and Regularized MLE Are Both Optimal for Top-K Rankingcited by 46
  8. 2019Practical Differentially Private Top-k Selection with Pay-what-you-get Compositioncited by 38
  9. 2017Tight Lower Bounds for Differentially Private Selectioncited by 33
  10. 2018Differentially Private False Discovery Rate Controlcited by 14
  11. 2017The Price of Selection in Differential Privacycited by 7
  12. 2015Private False Discovery Rate Controlcited by 6
2 more
  1. 2018Beyond Worst-Case Analysiscited by 6
  2. 2019Optimal Differential Privacy Composition for Exponential Mechanisms and the Cost of Adaptivitycited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 4; 2023: 4; 2024: 4; 2025: 2; 2026: 2.

16 papers.

Sort:

By area:

  1. 2023Zeroth-Order Optimization Meets Human Feedback: Provable Learning via Ranking Oraclescited by 34
  2. 2023A Fast Algorithm for Adaptive Private Mean Estimationcited by 11
  3. 2022Adaptive Private-K-Selection with Adaptive K and Application to Multi-label PATEcited by 9
  4. 2022On Noisy Evaluation in Federated Hyperparameter Tuningcited by 6
  5. 2023Hot PATE: Private Aggregation of Distributions for Diverse Taskcited by 3
  6. 2022Differentially Private Top-k Selection via Canonical Lipschitz Mechanismcited by 2
  7. 2024Feature Selection from Differentially Private Correlationscited by 2
  8. 2024The Correlated Gaussian Sparse Histogram Mechanismcited by 2
  9. 2022Majority Vote for Distributed Differentially Private Sign Selectioncited by 1
  10. 2023On the Computational Complexity of Private High-dimensional Model Selectioncited by 1
  11. 2025Improved Regret in Stochastic Decision-Theoretic Online Learning under Differential Privacycited by 1
  12. 2025Optimal Differentially Private Ranking from Pairwise Comparisonscited by 1
4 more
  1. 2026On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCAcited by 1
  2. 2024Unleash the Power of Ellipsis: Accuracy-enhanced Sparse Vector Technique with Exponential Noisecited by 0
  3. 2024Optimal Bounds for Private Minimum Spanning Trees via Input Perturbationcited by 0
  4. 2026Improved Private Sparse Covariance Estimation with Multiscale Threshold Testscited by 0