Title :

When Privacy Meets Partial Information: A Refined Analysis of Differentially Private Bandits

Author(s) :

Azize, Achraf [Auteur]
Scool [Scool]
Basu, Debabrota [Auteur]
Scool [Scool]

Conference title :

Advances in Neural Information Processing Systems

City :

New Orleans

Country :

Etats-Unis d'Amérique

Start date of the conference :

2022-12

English keyword(s) :

Differential privacy
Multiarmed bandit
Linear bandits
Regret Bounds
UCB policies

HAL domain(s) :

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]

English abstract : [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 ...
Show more >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.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL