mlsanityData to 7 Oct 2026

Adaptive Private-K-Selection with Adaptive K and Application to Multi-label PATE

arXiv 2203.16100 ↗First posted 30 Mar 2022cs.LG cs.CRcited by 9

Not on the map. Why?

Abstract (arXiv)

We provide an end-to-end Renyi DP based-framework for differentially private top-k selection. Unlike previous approaches, which require a data-independent choice on k, we propose to privately release a data-dependent choice of k such that the gap between k-th and the (k+1)st "quality" is large. This is achieved by a novel application of the Report-Noisy-Max. Not only does this eliminate one hyperparameter, the adaptive choice of k also certifies the stability of the top-k indices in the unordered set so we can release them using a variant of propose-test-release (PTR) without adding noise. We show that our construction improves the privacy-utility trade-offs compared to the previous top-k selection algorithms theoretically and empirically. Additionally, we apply our algorithm to "Private Aggregation of Teacher Ensembles (PATE)" in multi-label classification tasks with a large number of labels and show that it leads to significant performance gains.

Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). Builds on 16 of its 38 references that are in the map. First posted on arXiv 30 Mar 2022.

Builds on

16 of 38 references.

References · 16

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2014Deep Learning Face Attributes in the Wildcited by 3,679
  3. 2017Renyi Differential Privacycited by 643
  4. 2016Semi-supervised Knowledge Transfer for Deep Learning from Private Training Datacited by 347
  5. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 339
  6. 2013The Composition Theorem for Differential Privacycited by 290
  7. 2018Scalable Private Learning with PATEcited by 266
  8. 2019Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimationcited by 51
  9. 2019Practical Differentially Private Top-k Selection with Pay-what-you-get Compositioncited by 38
  10. 2016Understanding the Sparse Vector Technique for Differential Privacycited by 27
  11. 2021Oneshot Differentially Private Top-k Selectioncited by 16
  12. 2018Differentially Private False Discovery Rate Controlcited by 14
4 more
  1. 2021The Permute-and-Flip Mechanism is Identical to Report-Noisy-Max with Exponential Noisecited by 14
  2. 2022A Joint Exponential Mechanism For Differentially Private Top-kcited by 9
  3. 2014The Large Margin Mechanism for Differentially Private Maximizationcited by 7
  4. 2015Private False Discovery Rate Controlcited by 6

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 3; 2024: 4; 2025: 1.

9 papers.

  1. 2023DP-OPT: Make Large Language Model Your Privacy-Preserving Prompt Engineercited by 56
  2. 2023Privacy-Preserving In-Context Learning for Large Language Modelscited by 50
  3. 2024Permute-and-Flip: An optimally stable and watermarkable decoder for LLMscited by 17
  4. 2024Open LLMs are Necessary for Current Private Adaptations and Outperform their Closed Alternativescited by 12
  5. 2024Data-adaptive Differentially Private Prompt Synthesis for In-Context Learningcited by 10
  6. 2023Quantifying and Defending against Privacy Threats on Federated Knowledge Graph Embeddingcited by 7
  7. 2024Privacy Profiles for Private Selectioncited by 2
  8. 2025Differentially Private In-Context Learning with Nearest Neighbor Searchcited by 1
  9. 2022An Ensemble Teacher-Student Learning Approach with Poisson Sub-sampling to Differential Privacy Preserving Speech Recognitioncited by 0