Optimal Best Arm Identification under Differential Privacy
Marc JourdanEPFL, Lausanne, Switzerland [email protected], Achraf AzizeFairPlay Joint Team, CREST, ENSAE Paris [email protected] · 2025
Read Optimal Best Arm Identification under Differential Privacy by Marc JourdanEPFL, Lausanne, Switzerland [email protected], Achraf AzizeFairPlay Joint Team, CREST, ENSAE Paris [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-17348.txt.
Introduction
Picking the best option from several uncertain ones, while keeping each person data private, is the tension at the heart of a study by Marc Jourdan and Achraf Azize. Their setting is best arm identification, used in sensitive trials and user studies, under a global differential privacy rule that limits what the full data set can reveal about anyone. Known methods in the private setting sat far from the proven lower limits on how many samples any method must use.
Jourdan and Azize close most of that gap for outcomes that follow a coin flip style distribution. They prove a sharper lower bound built on a new cost measure, then design a stopping rule and a top two sampling rule to match it. Their method stays within a small constant factor of the bound and beats existing private methods across privacy budgets.
Catalog record
| CREATOR | Marc JourdanEPFL, Lausanne, Switzerland [email protected], Achraf AzizeFairPlay Joint Team, CREST, ENSAE Paris [email protected] |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 372 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-17348