Research map / Federated learning and privacy / Differential privacy
Optimal Best Arm Identification under Differential Privacy
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Closes most of the gap between lower and upper bounds for fixed-confidence best arm identification under global epsilon-DP for Bernoulli bandits, via a new d_epsilon-based lower bound, a geometric-grid private estimator with GLR stopping, and a DP Top Two sampler (DP-TT) matching the lower bound up to a constant below 8.
Problem
Fixed-confidence best arm identification with Bernoulli arms under global epsilon-differential privacy; existing lower and upper sample complexity bounds have a significant gap.
Approach
Replace the KL (non-private) or min{KL, eps TV} transportation cost with the d_epsilon divergence that interpolates between KL and epsilon-scaled TV, use it in a tighter lower bound, a GLR stopping rule and a Top Two sampler, and estimate means privately with arm-dependent geometric batching that does not forget past observations.
Key results
- DP-TT matches the new lower bound up to a constant smaller than 8 (4T*_{eps,1/2} <= 8T*_eps) for any privacy budget eps.
- DP-TT outperforms AdaP-TT, AdaP-TT* and DP-SE on the tested Bernoulli instances for all tested eps (0.001 to 125).
- In the low privacy regime DP-TT requires about twice the samples of non-private EB-TCI-beta.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DP-TT with the dε-inspired transportation costs | Fixed-confidence global-DP Bernoulli BAI · All tested Bernoulli instances and privacy budgets ε | empirical stopping time | Helped |
| Increase ε within the low-privacy regime | DP-TT · Bernoulli instances in the low-privacy regime | empirical stopping time | No clear effect |
| Use DP-TT with (η,β)=(1,1/2) | Fixed-confidence global-DP Bernoulli BAI · Bernoulli instances with distinct means, any ε | asymptotic expected sample complexity / log(1/δ): 4T^{\star}_{\epsilon, 1/2}(\boldsymbol{\nu}) \le 8T^{\star}_{\epsilon}(\boldsymbol{\nu}) | Helped |
| Use a fixed β=1/2 target allocation instead of the unconstrained optimal allocation | Top Two sampling · Bernoulli instances with distinct means | characteristic time: T^{\star}_{\epsilon,1/2}(\bm \nu) \le 2 T^{\star}_{\epsilon}(\bm \nu) | Hurt |
Surprising findings
- In the low privacy regime DP-TT needs about twice the samples of the non-private EB-TCI-beta algorithm.
Limitations
- Stopping threshold is a sum of per-arm thresholds, scaling as 2 log(1/delta), losing a factor 2 asymptotically.
- Results are for Bernoulli distributions; extending to other distributions requires computing d_epsilon numerically, which increases computational cost.
- Assumes a unique best arm with distinct means; sample complexity blows up near ties.
Experimental setup
Benchmarks: Bernoulli instance mu1=(0.95,0.9,0.9,0.9,0.5) Bernoulli instance mu2=(0.75,0.7,0.7,0.7,0.7)
Metrics: empirical stopping time (sample complexity)
Baselines: AdaP-TT AdaP-TT* DP-SE EB-TCI-beta (non-private)
Builds on: Top Two sampling Track-and-Stop AdaP-TT d_epsilon divergence (regret minimisation) Laplace mechanism
Closest papers by meaning
- Asymptotically Optimal Best Arm Identification with Fixed-Budget under Differential Privacy (NeurIPS 2026 · similarity 0.93)
- Fixed-Budget Differentially Private Best Arm Identification (ICLR 2024 · similarity 0.92)
- Locally Optimal Private Sampling: Beyond the Global Minimax (NeurIPS 2025 · similarity 0.87)
- On Inherent Privacy of Posterior Sampling: A Unified R\'enyi-Divergence Framework (NeurIPS 2026 · similarity 0.87)
- Fixing the Loose Brake: Exponential-Tailed Stopping Time in Best Arm Identification (ICML 2025 · similarity 0.86)
- Fixed Confidence Best Arm Identification in the Bayesian Setting (NeurIPS 2024 · 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.