Research map / Federated learning and privacy / Differential privacy

Asymptotically Optimal Best Arm Identification with Fixed-Budget under Differential Privacy

NeurIPS 2026 · Federated learning and privacy › Differential privacy · approach: Privacy accounting and mechanisms · 0 citations (OpenAlex)

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.

Studies fixed-budget Bernoulli best-arm identification under pure epsilon-DP, derives a privacy-aware transportation exponent lower bound, and proposes AO-Pri-BAI (Laplace-tree private estimates, min-max Gibbs challenger sampling, AdaHedge allocation) claimed to match it asymptotically.

Problem

Fixed-budget best arm identification must protect the full adaptive transcript under pure epsilon-differential privacy, and the optimal error-probability decay rate under this constraint is unknown.

Approach

A privacy-aware transportation exponent with reversed argument order relative to fixed-confidence DP-BAI characteristic time, a matching-exponent algorithm combining continual-release Laplace-tree statistics, Gibbs sampling of private challengers, and AdaHedge sampling-design learning.

Key results

• On a 50-arm synthetic instance (epsilon=0.1, 500 trials), AO-Pri-BAI clearly dominates DP-TT-FB and Uniform in moderate and large budgets, approaching perfect accuracy while DP-TT-FB plateaus around mid-0.8s.
• On a 17-arm instance with a small gap, AO-Pri-BAI achieves higher accuracy than DP-BAI once the budget is moderately large.

Surprising findings

• DP-TT-FB, a fixed-confidence method adapted to fixed budget, plateaus in accuracy as GPE updates slow down over time.

Limitations

• The upper bound is for the conditional error probability given the history, not directly the unconditional error probability, so the exponents do not establish a matching unconditional characterization.
• Results are restricted to Bernoulli rewards; extension to other reward distributions is only outlined.
• Experiments are limited to synthetic instances with a single epsilon=0.1 setting.

Experimental setup

Benchmarks: synthetic 50-arm Bernoulli instance synthetic 17-arm instance

Metrics: empirical accuracy (probability of correct recommendation)

Baselines: Uniform DP-TT-FB DP-BAI

Builds on: Track-and-Stop characteristic time (Garivier and Kaufmann) AdaHedge Laplace-tree continual release DP-BAI fixed-confidence transportation cost (Azize and Jourdan)

Closest papers by meaning

• Fixed-Budget Differentially Private Best Arm Identification (ICLR 2024 · similarity 0.95)
• On the Complexity of Differentially Private Best-Arm Identification with Fixed Confidence (NeurIPS 2023 · similarity 0.94)
• Optimal Best Arm Identification under Differential Privacy (NeurIPS 2025 · similarity 0.93)
• Optimal Multi-Fidelity Best-Arm Identification (NeurIPS 2024 · similarity 0.89)
• Balancing Performance and Costs in Best Arm Identification (NeurIPS 2025 · similarity 0.88)
• Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits (NeurIPS 2024 · similarity 0.87)