Federated Linear Contextual Bandits with User-level Differential Privacy
Federated Linear Contextual Bandits with User-level Differential Privacy
复制标题
DOI：
10.48550/arxiv.2306.05275
复制
发表时间：
2023-06
期刊：
影响因子：
--
通讯作者：
Ruiquan Huang;Huanyu Zhang;Luca Melis;Milan Shen;Meisam Hajzinia;J. Yang
中科院分区：
文献类型：
--
作者：
Ruiquan Huang;Huanyu Zhang;Luca Melis;Milan Shen;Meisam Hajzinia;J. Yang
本文研究了用户级差分隐私（DP）概念下的联合线性上下文强盗。我们首先引入一个统一的联邦老虎机框架，该框架可以在顺序决策设置中容纳 DP 的各种定义。然后，我们在联邦强盗框架中正式引入用户级中央DP（CDP）和本地DP（LDP），并研究联邦线性上下文强盗模型中学习遗憾和相应DP保证之间的基本权衡。对于 CDP，我们提出了一种称为 $\texttt{ROBIN}$ 的联合算法，并通过在满足用户级 DP 时推导出几乎匹配的后悔上限和下限，表明该算法在客户端数量 $M$ 和隐私预算 $\varepsilon$ 方面接近最优。对于LDP，我们得到了几个下界，表明在用户级$(\varepsilon,\delta)$-LDP下的学习在不同条件下必须遭受至少$\min\{1/\varepsilon,M\}$或$\min\{1/\sqrt{\varepsilon},\sqrt{M}\}$的遗憾爆炸因子。
This paper studies federated linear contextual bandits under the notion of user-level differential privacy (DP). We first introduce a unified federated bandits framework that can accommodate various definitions of DP in the sequential decision-making setting. We then formally introduce user-level central DP (CDP) and local DP (LDP) in the federated bandits framework, and investigate the fundamental trade-offs between the learning regrets and the corresponding DP guarantees in a federated linear contextual bandits model. For CDP, we propose a federated algorithm termed as $\texttt{ROBIN}$ and show that it is near-optimal in terms of the number of clients $M$ and the privacy budget $\varepsilon$ by deriving nearly-matching upper and lower regret bounds when user-level DP is satisfied. For LDP, we obtain several lower bounds, indicating that learning under user-level $(\varepsilon,\delta)$-LDP must suffer a regret blow-up factor at least $\min\{1/\varepsilon,M\}$ or $\min\{1/\sqrt{\varepsilon},\sqrt{M}\}$ under different conditions.