Research map / Federated learning and privacy / Differential privacy
Oneshot Differentially Private Top-k Selection
Gang Qiao, Weijie Su, Li Zhang
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Select all k items from one noisy ranking rather than running Report Noisy Max k times | Oneshot Laplace · Top-k selection | number of selection passes: k times -> once | Improved |
| Use one-shot selection with Laplace noise calibrated for approximate privacy | Top-k selection · Top-k selection | noise scale for (ε,δ)-differential privacy: \widetilde{O}(\sqrt{k}/\eps) | Improved |
| Apply the one-shot mechanism to stationary-distribution scores from pairwise comparisons | Oneshot differentially private spectral method · Private pairwise comparison top-k | noise scale for (ε,δ)-differential privacy: \lambda=\frac{8s\sqrt{k\log(m/\delta)}}{\e} | Improved |
| Use the one-shot mechanism when adjacent inputs have a sufficiently large minimum gap | Oneshot Laplace · Top-k selection with \Delta \ge 20 \lambda and m \le 8\times 10^6 | probability of returning the true top-k set: p(\Delta)>0.99 | Improved |
Closest papers by meaning
- Faster Differentially Private Top-$k$ Selection: A Joint Exponential Mechanism with Pruning (NeurIPS 2024 · similarity 0.91)
- Privacy Profiles for Private Selection (ICML 2024 · similarity 0.86)
- Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph (NeurIPS 2025 · similarity 0.86)
- Sort, Partition, Randomize: Optimal Binary Hypothesis Testing under Local Differential Privacy (NeurIPS 2026 · similarity 0.86)
- Approximate Differential Privacy of the $\ell_2$ Mechanism (ICML 2025 · similarity 0.85)
- Differentially Private Graph Diffusion with Applications in Personalized PageRanks (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
