Practical Differentially Private Top-k Selection with Pay-what-you-get Composition
Authors: David Durfee, Ryan M. Rogers
NeurIPS 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We design algorithms that ensures (approximate) (ε, δ > 0)-differential privacy and only needs access to the true topk elements from the data for any chosen k k. We design different algorithms for either setting so that the privacy parameter ε needs to scale with either in the restricted sensitivity setting or k in the unrestricted setting. 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. |
| Researcher Affiliation | Industry | David Durfee1 and Ryan Rogers1 1Data Science Applied Research, Linked In |
| Pseudocode | Yes | Algorithm 1 Limit Domk, k; Top-k from the k k limited domain Algorithm 2 multi Limit Domk ,ℓ ; Multiple queries to limited domain |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code or links to a code repository for the methodology described. |
| Open Datasets | No | The paper is theoretical and primarily focuses on algorithm design, privacy guarantees, and composition theorems. It does not conduct empirical experiments that involve training models on datasets. |
| Dataset Splits | No | The paper is theoretical and focuses on algorithm design and privacy guarantees. It does not conduct empirical experiments that would require validation splits. |
| Hardware Specification | No | The paper is theoretical and does not describe empirical experiments. Therefore, no hardware specifications for running experiments are provided. |
| Software Dependencies | No | The paper is theoretical and does not describe empirical experiments with specific software implementations. Therefore, no specific software dependencies with version numbers are mentioned. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and privacy guarantees. It does not detail an experimental setup with hyperparameters or training configurations, as no empirical experiments are conducted. |