Differentially Private Best-Arm Identification

• URL: http://arxiv.org/abs/2406.06408v1
• Date: Mon, 10 Jun 2024 16:02:48 GMT
• Title: Differentially Private Best-Arm Identification
• Authors: Achraf Azize, Marc Jourdan, Aymen Al Marjani, Debabrota Basu,
• Abstract summary: Best Arm Identification (BAI) problems are progressively used for data-sensitive applications. 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.
• Score: 14.916947598339988
• License: http://creativecommons.org/licenses/by/4.0/
• 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 $\delta$-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 papers

• Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
  We study best arm identification (BAI) in linear bandits in the fixed-budget regime under differential privacy constraints. We derive a minimax lower bound on the error probability, and demonstrate that the lower and the upper bounds decay exponentially in $T$.
  arXiv  Detail & Related papers  (2024-01-17T09:23:25Z)
• A Generalized Shuffle Framework for Privacy Amplification: Strengthening Privacy Guarantees and Enhancing Utility [4.7712438974100255]
  We show how to shuffle $(epsilon_i,delta_i)$-PLDP setting with personalized privacy parameters. We prove that shuffled $(epsilon_i,delta_i)$-PLDP process approximately preserves $mu$-Gaussian Differential Privacy with mu = sqrtfrac2sum_i=1n frac1-delta_i1+eepsilon_i-max_ifrac1-delta_i1+e
  arXiv  Detail & Related papers  (2023-12-22T02:31:46Z)
• On the Complexity of Differentially Private Best-Arm Identification with Fixed Confidence [16.295693624977563]
  We study the problem of Best Arm Identification with fixed confidence under $epsilon$-global Differential Privacy. Our lower bound suggests the existence of two privacy regimes depending on the privacy budget. We propose AdaP-TT, an $epsilon$-global DP variant of the Top Two algorithm.
  arXiv  Detail & Related papers  (2023-09-05T13:07:25Z)
• When Privacy Meets Partial Information: A Refined Analysis of Differentially Private Bandits [4.964737844687583]
  We study the problem of multi-armed bandits with $epsilon$-global Differential Privacy (DP) We instantiate $epsilon$-global DP extensions of UCB and KL-UCB algorithms, namely AdaP-UCB and AdaP-KLUCB. AdaP-KLUCB is the first algorithm that both satisfies $epsilon$-global DP and yields a regret upper bound that matches the problem-dependent lower bound up to multiplicative constants.
  arXiv  Detail & Related papers  (2022-09-06T15:26:24Z)
• Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization [94.06564567766475]
  DP-SGD and DP-NSGD mitigate the risk of large models memorizing sensitive training data. We show that these two algorithms achieve similar best accuracy while DP-NSGD is comparatively easier to tune than DP-SGD.
  arXiv  Detail & Related papers  (2022-06-27T03:45:02Z)
• Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent [69.14164921515949]
  We characterize privacy guarantees for individual examples when releasing models trained by DP-SGD. We find that most examples enjoy stronger privacy guarantees than the worst-case bound. This implies groups that are underserved in terms of model utility simultaneously experience weaker privacy guarantees.
  arXiv  Detail & Related papers  (2022-06-06T13:49:37Z)
• Smoothed Differential Privacy [55.415581832037084]
  Differential privacy (DP) is a widely-accepted and widely-applied notion of privacy based on worst-case analysis. In this paper, we propose a natural extension of DP following the worst average-case idea behind the celebrated smoothed analysis. We prove that any discrete mechanism with sampling procedures is more private than what DP predicts, while many continuous mechanisms with sampling procedures are still non-private under smoothed DP.
  arXiv  Detail & Related papers  (2021-07-04T06:55:45Z)
• Learning with User-Level Privacy [61.62978104304273]
  We analyze algorithms to solve a range of learning tasks under user-level differential privacy constraints. Rather than guaranteeing only the privacy of individual samples, user-level DP protects a user's entire contribution. We derive an algorithm that privately answers a sequence of $K$ adaptively chosen queries with privacy cost proportional to $tau$, and apply it to solve the learning tasks we consider.
  arXiv  Detail & Related papers  (2021-02-23T18:25:13Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  We propose differentially private (DP) algorithms for bound non-dimensional optimization. We demonstrate two popular deep learning methods on the empirical advantages over standard gradient methods.
  arXiv  Detail & Related papers  (2020-06-24T06:01:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.