When Privacy Meets Partial Information: A ...
Type de document :
Communication dans un congrès avec actes
Titre :
When Privacy Meets Partial Information: A Refined Analysis of Differentially Private Bandits
Auteur(s) :
Titre de la manifestation scientifique :
Advances in Neural Information Processing Systems
Ville :
New Orleans
Pays :
Etats-Unis d'Amérique
Date de début de la manifestation scientifique :
2022-12
Mot(s)-clé(s) en anglais :
Differential privacy
Multiarmed bandit
Linear bandits
Regret Bounds
UCB policies
Multiarmed bandit
Linear bandits
Regret Bounds
UCB policies
Discipline(s) HAL :
Informatique [cs]/Apprentissage [cs.LG]
Statistiques [stat]/Machine Learning [stat.ML]
Informatique [cs]/Ordinateur et société [cs.CY]
Mathématiques [math]/Statistiques [math.ST]
Informatique [cs]/Théorie de l'information [cs.IT]
Informatique [cs]/Intelligence artificielle [cs.AI]
Statistiques [stat]/Machine Learning [stat.ML]
Informatique [cs]/Ordinateur et société [cs.CY]
Mathématiques [math]/Statistiques [math.ST]
Informatique [cs]/Théorie de l'information [cs.IT]
Informatique [cs]/Intelligence artificielle [cs.AI]
Résumé en anglais : [en]
We study the problem of multi-armed bandits with $\epsilon$-global Differential Privacy (DP). First, we prove the minimax and problem-dependent regret lower bounds for stochastic and linear bandits that quantify the hardness ...
Lire la suite >We study the problem of multi-armed bandits with $\epsilon$-global Differential Privacy (DP). First, we prove the minimax and problem-dependent regret lower bounds for stochastic and linear bandits that quantify the hardness of bandits with $\epsilon$-global DP. These bounds suggest the existence of two hardness regimes depending on the privacy budget $\epsilon$. In the high-privacy regime (small $\epsilon$), the hardness depends on a coupled effect of privacy and partial information about the reward distributions. In the low-privacy regime (large $\epsilon$), bandits with $\epsilon$-global DP are not harder than the bandits without privacy. For stochastic bandits, we further propose a generic framework to design a near-optimal $\epsilon$ global DP extension of an index-based optimistic bandit algorithm. The framework consists of three ingredients: the Laplace mechanism, arm-dependent adaptive episodes, and usage of only the rewards collected in the last episode for computing private statistics. Specifically, 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.Lire moins >
Lire la suite >We study the problem of multi-armed bandits with $\epsilon$-global Differential Privacy (DP). First, we prove the minimax and problem-dependent regret lower bounds for stochastic and linear bandits that quantify the hardness of bandits with $\epsilon$-global DP. These bounds suggest the existence of two hardness regimes depending on the privacy budget $\epsilon$. In the high-privacy regime (small $\epsilon$), the hardness depends on a coupled effect of privacy and partial information about the reward distributions. In the low-privacy regime (large $\epsilon$), bandits with $\epsilon$-global DP are not harder than the bandits without privacy. For stochastic bandits, we further propose a generic framework to design a near-optimal $\epsilon$ global DP extension of an index-based optimistic bandit algorithm. The framework consists of three ingredients: the Laplace mechanism, arm-dependent adaptive episodes, and usage of only the rewards collected in the last episode for computing private statistics. Specifically, 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.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.archives-ouvertes.fr/hal-03781600/document
- Accès libre
- Accéder au document
- http://arxiv.org/pdf/2209.02570
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03781600/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03781600/document
- Accès libre
- Accéder au document
- When_Privacy_Meets_Partial_Information-2.pdf
- Accès libre
- Accéder au document
- 2209.02570
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- When_Privacy_Meets_Partial_Information-2.pdf
- Accès libre
- Accéder au document