Federated Linear Contextual Bandits with User-level Differential Privacy

Ruiquan Huang, Huanyu Zhang, Luca Melis, Milan Shen, Meisam Hejazinia, Jing Yang
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:14060-14095, 2023.

Abstract

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 ROBIN and show that it is near-optimal in terms of the number of clients M and the privacy budget ε 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 (ε,δ)-LDP must suffer a regret blow-up factor at least min or \min\{1/\sqrt{\varepsilon},\sqrt{M}\} under different conditions.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-huang23q, title = {Federated Linear Contextual Bandits with User-level Differential Privacy}, author = {Huang, Ruiquan and Zhang, Huanyu and Melis, Luca and Shen, Milan and Hejazinia, Meisam and Yang, Jing}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {14060--14095}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/huang23q/huang23q.pdf}, url = {https://proceedings.mlr.press/v202/huang23q.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Federated Linear Contextual Bandits with User-level Differential Privacy %A Ruiquan Huang %A Huanyu Zhang %A Luca Melis %A Milan Shen %A Meisam Hejazinia %A Jing Yang %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-huang23q %I PMLR %P 14060--14095 %U https://proceedings.mlr.press/v202/huang23q.html %V 202 %X 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.
APA
Huang, R., Zhang, H., Melis, L., Shen, M., Hejazinia, M. & Yang, J.. (2023). Federated Linear Contextual Bandits with User-level Differential Privacy. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:14060-14095 Available from https://proceedings.mlr.press/v202/huang23q.html.

Related Material