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

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

## Key facts

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

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Deep Learning Face Attributes in the Wild](https://mlsanity.com/paper/1411.7766/) (2014)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data](https://mlsanity.com/paper/1610.05755/) (2016)
- [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)
- [Scalable Private Learning with PATE](https://mlsanity.com/paper/1802.08908/) (2018)
- [Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation](https://mlsanity.com/paper/1906.02830/) (2019)
- [Practical Differentially Private Top-k Selection with Pay-what-you-get Composition](https://mlsanity.com/paper/1905.04273/) (2019)
- [Understanding the Sparse Vector Technique for Differential Privacy](https://mlsanity.com/paper/1603.01699/) (2016)
- [Oneshot Differentially Private Top-k Selection](https://mlsanity.com/paper/2105.08233/) (2021)
- [Differentially Private False Discovery Rate Control](https://mlsanity.com/paper/1807.04209/) (2018)
- [The Permute-and-Flip Mechanism is Identical to Report-Noisy-Max with Exponential Noise](https://mlsanity.com/paper/2105.07260/) (2021)
- [A Joint Exponential Mechanism For Differentially Private Top-k](https://mlsanity.com/paper/2201.12333/) (2022)
- [The Large Margin Mechanism for Differentially Private Maximization](https://mlsanity.com/paper/1409.2177/) (2014)
- [Private False Discovery Rate Control](https://mlsanity.com/paper/1511.03803/) (2015)

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

- [DP-OPT: Make Large Language Model Your Privacy-Preserving Prompt Engineer](https://mlsanity.com/paper/2312.03724/) (2023)
- [Privacy-Preserving In-Context Learning for Large Language Models](https://mlsanity.com/paper/2305.01639/) (2023)
- [Permute-and-Flip: An optimally stable and watermarkable decoder for LLMs](https://mlsanity.com/paper/2402.05864/) (2024)
- [Open LLMs are Necessary for Current Private Adaptations and Outperform their Closed Alternatives](https://mlsanity.com/paper/2411.05818/) (2024)
- [Data-adaptive Differentially Private Prompt Synthesis for In-Context Learning](https://mlsanity.com/paper/2410.12085/) (2024)
- [Quantifying and Defending against Privacy Threats on Federated Knowledge Graph Embedding](https://mlsanity.com/paper/2304.02932/) (2023)
- [Privacy Profiles for Private Selection](https://mlsanity.com/paper/2402.06701/) (2024)
- [Differentially Private In-Context Learning with Nearest Neighbor Search](https://mlsanity.com/paper/2511.04332/) (2025)
- [An Ensemble Teacher-Student Learning Approach with Poisson Sub-sampling to Differential Privacy Preserving Speech Recognition](https://mlsanity.com/paper/2210.06382/) (2022)

## 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.