Research map / Federated learning and privacy / Differential privacy
On the Complexity of Differentially Private Best-Arm Identification with Fixed Confidence
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (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 |
|---|---|---|---|
| Use Ada-TT instead of DP-SE | Fixed-confidence differentially private best-arm identification · Bernoulli instances tested | stopping time | Helped |
| Increase privacy by reducing epsilon | Ada-TT · Bernoulli instances tested | stopping time | Hurt |
| Increase epsilon above 0.2 | Ada-TT · Bernoulli instances tested | stopping time | No clear effect |
| Use adaptive sampling rather than uniform sampling within phases | Private fixed-confidence best-arm identification · Bernoulli instances tested | stopping time | Helped |
| Add per-arm doubling episodes and forget rewards from previous phases (ablation) | Ada-TT · Asymptotic sample complexity | sample complexity: 4 T_{\mathrm{KL},\beta}^\star(\boldsymbol{\mu}) | Hurt |
| Add Laplace noise to empirical means (ablation) | Ada-TT · Asymptotic sample complexity | sample complexity: 4 T_{\mathrm{KL},\beta}^\star(\boldsymbol{\mu}) \left( 1+ \sqrt{1 + \frac{\Delta^2_{\max}}{2\epsilon^2}} \right) | Hurt |
| Use a private GLR threshold instead of the non-private threshold (ablation) | Ada-TT stopping rule · Asymptotic sample complexity | sample complexity | Hurt |
| Use privacy with sufficiently large epsilon | Fixed-confidence best-arm identification · Low-privacy regime | sample complexity lower bound | No clear effect |
Closest papers by meaning
- Optimal Best Arm Identification under Differential Privacy (NeurIPS 2025 · similarity 0.96)
- Asymptotically Optimal Best Arm Identification with Fixed-Budget under Differential Privacy (NeurIPS 2026 · similarity 0.94)
- Fixed-Budget Differentially Private Best Arm Identification (ICLR 2024 · similarity 0.92)
- Optimal Multi-Fidelity Best-Arm Identification (NeurIPS 2024 · similarity 0.86)
- Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback (NeurIPS 2026 · similarity 0.86)
- Certification for Differentially Private Prediction in Gradient-Based Training (ICML 2025 · similarity 0.86)
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.