On the Complexity of Differentially Private Best-Arm Identification with Fixed Confidence
This addresses privacy concerns in sensitive applications like clinical trials and hyperparameter tuning, providing theoretical guarantees for differentially private bandit algorithms.
The paper tackles the problem of Best Arm Identification with fixed confidence under differential privacy constraints, deriving a lower bound on sample complexity that reveals two privacy regimes and proposing an algorithm (AdaP-TT) whose upper bound matches the lower bound in the high-privacy regime.
Best Arm Identification (BAI) problems are progressively used for data-sensitive applications, such as designing adaptive clinical trials, tuning hyper-parameters, and conducting user studies to name a few. Motivated by the data privacy concerns invoked by these applications, we study the problem of BAI with fixed confidence under $ε$-global Differential Privacy (DP). First, to quantify the cost of privacy, we derive a lower bound on the sample complexity of any $δ$-correct BAI algorithm satisfying $ε$-global DP. Our lower bound suggests the existence of two privacy regimes depending on the privacy budget $ε$. In the high-privacy regime (small $ε$), the hardness depends on a coupled effect of privacy and a novel information-theoretic quantity, called the Total Variation Characteristic Time. In the low-privacy regime (large $ε$), the sample complexity lower bound reduces to the classical non-private lower bound. Second, we propose AdaP-TT, an $ε$-global DP variant of the Top Two algorithm. AdaP-TT runs in arm-dependent adaptive episodes and adds Laplace noise to ensure a good privacy-utility trade-off. We derive an asymptotic upper bound on the sample complexity of AdaP-TT that matches with the lower bound up to multiplicative constants in the high-privacy regime. Finally, we provide an experimental analysis of AdaP-TT that validates our theoretical results.