Differentially Private Best-Arm Identification

arXiv:2406.06408v2 Announce Type: replace-cross Abstract: 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. Motivated by the data privacy concerns invoked by these applications, we study the problem of BAI with fixed confidence in both the local and central models, i.e. epsilon-local and epsilon-global Differential Privacy (DP). First, to quantify the cost of privacy, we derive lower bounds on the sample complexity of any elta-correct BAI algorithm satisfying epsilon-global DP or epsilon-local DP. Our lower bounds suggest the existence of two privacy regimes. In the high-privacy regime, the hardness depends on a coupled effect of privacy and novel information-theoretic quantities involving the Total Variation. In the low-privacy regime, the lower bounds reduce to the non-private lower bounds. We propose epsilon-local DP and epsilon-global DP variants of a Top Two algorithm, namely CTB-TT and AdaP-TT*, respectively. For epsilon-local DP, CTB-TT is asymptotically optimal by plugging in a private estimator of the means based on Randomised Response. For epsilon-global DP, our private estimator of the mean runs in arm-dependent adaptive episodes and adds Laplace noise to ensure a good privacy-utility trade-off. By adapting the transportation costs, the expected sample complexity of AdaP-TT* reaches the asymptotic lower bound up to multiplicative constants.

Related

• ConfusionPrompt: Practical Private Inference for Online Large Language Models
• Auditing Black-Box LLM APIs with a Rank-Based Uniformity Test
• CHiQPM: Calibrated Hierarchical Interpretable Image Classification
• Learning to Query History: Nonstationary Classification via Learned Retrieval

Source: arXiv cs.LG | 2026-04-10