Oneshot Differentially Private Top-k Selection
Authors: Gang Qiao, Weijie Su, Li Zhang
ICML 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we present the oneshot Laplace mechanism, which generalizes the wellknown Report Noisy Max (Dwork & Roth, 2014) mechanism to reporting noisy top-k elements. We show that the oneshot Laplace mechanism with a noise level of e O( k/ε) is approximately differentially private. In this paper, we show that the oneshot Laplace mechanism can achieve utility comparable to those obtained from the peeling procedure (see Theorems 2.1 and 2.2 for the precise statements). Our proof directly bounds the privacy loss without the help of the composition theorems. The technical tools developed for proving the privacy of the oneshot top-k algorithm in this section can be applied in many other settings. We provide the proof sketch to our main result and leave most of the technical details to the supplementary material. |
| Researcher Affiliation | Collaboration | 1Department of Statistics, University of Michigan, Ann Arbor, MI, USA. 2The Wharton School, University of Pennsylvania, Philadelphia, PA, USA. 3Google Research, Mountain View, CA, USA. |
| Pseudocode | Yes | Algorithm 1 The Oneshot Laplace Mechanism Mos for Privately Reporting Minimum k Elements; Algorithm 2 The spectral method for pairwise comparison; Algorithm 3 The oneshot differentially private spectral method |
| Open Source Code | No | The paper does not provide any statement about releasing source code or include a link to a code repository. |
| Open Datasets | No | The paper is theoretical and focuses on algorithm design and proofs of privacy and utility. It does not describe any experimental setup involving training on specific datasets. |
| Dataset Splits | No | The paper is theoretical and focuses on algorithm design and proofs. It does not describe empirical experiments with data, and thus, no dataset split information for validation is provided. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithm design and mathematical proofs. It does not describe any experiments that would require specific hardware, and thus no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical, focusing on mathematical mechanisms and proofs. It does not describe any implementation details that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical, presenting algorithms and proofs, and does not include empirical experiments. Therefore, there is no mention of specific experimental setup details such as hyperparameters or training configurations. |