• English
    • français
  • Aide
  •  | 
  • Contact
  •  | 
  • À Propos
  •  | 
  • Ouvrir une session
  • Portail HAL
  •  | 
  • Pages Pro Chercheurs
  • EN
  •  / 
  • FR
Voir le document 
  •   Accueil de LillOA
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • Voir le document
  •   Accueil de LillOA
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • Voir le document
JavaScript is disabled for your browser. Some features of this site may not work without it.

When Privacy Meets Partial Information: A ...
  • BibTeX
  • CSV
  • Excel
  • RIS

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) :
Azize, Achraf [Auteur]
Scool [Scool]
Basu, Debabrota [Auteur]
Scool [Scool]
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
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]
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 >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Collections :
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Source :
Harvested from HAL
Fichiers
Thumbnail
  • https://hal.archives-ouvertes.fr/hal-03781600/document
  • Accès libre
  • Accéder au document
Thumbnail
  • http://arxiv.org/pdf/2209.02570
  • Accès libre
  • Accéder au document
Thumbnail
  • https://hal.archives-ouvertes.fr/hal-03781600/document
  • Accès libre
  • Accéder au document
Thumbnail
  • https://hal.archives-ouvertes.fr/hal-03781600/document
  • Accès libre
  • Accéder au document
Thumbnail
  • When_Privacy_Meets_Partial_Information-2.pdf
  • Accès libre
  • Accéder au document
Thumbnail
  • 2209.02570
  • Accès libre
  • Accéder au document
Thumbnail
  • document
  • Accès libre
  • Accéder au document
Thumbnail
  • document
  • Accès libre
  • Accéder au document
Thumbnail
  • When_Privacy_Meets_Partial_Information-2.pdf
  • Accès libre
  • Accéder au document
Université de Lille

Mentions légales
Accessibilité : non conforme
Université de Lille © 2017