Open Problem: What is the Complexity of Joint Differential Privacy in Linear Contextual Bandits?

Achraf Azize, Debabrota Basu
Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5306-5311, 2024.

Abstract

Contextual bandits serve as a theoretical framework to design recommender systems, which often rely on user-sensitive data, making privacy a critical concern. However, a significant gap remains between the known upper and lower bounds on the regret achievable in linear contextual bandits under Joint Differential Privacy (JDP), which is a popular privacy definition used in this setting. In particular, the best regret upper bound is known to be $O\left(d \sqrt{T} \log(T) + \textcolor{blue}{d^{3/4} \sqrt{T \log(1/\delta)} / \sqrt{\epsilon}} \right)$, while the lower bound is $\Omega \left(\sqrt{d T \log(K)} + \textcolor{blue}{d/(\epsilon + \delta)}\right)$. We discuss the recent progress on this problem, both from the algorithm design and lower bound techniques, and posit the open questions.

Cite this Paper

BibTeX
@InProceedings{pmlr-v247-azize24a, title = {Open Problem: What is the Complexity of Joint Differential Privacy in Linear Contextual Bandits?}, author = {Azize, Achraf and Basu, Debabrota}, booktitle = {Proceedings of Thirty Seventh Conference on Learning Theory}, pages = {5306--5311}, year = {2024}, editor = {Agrawal, Shipra and Roth, Aaron}, volume = {247}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v247/azize24a/azize24a.pdf}, url = {https://proceedings.mlr.press/v247/azize24a.html}, abstract = {Contextual bandits serve as a theoretical framework to design recommender systems, which often rely on user-sensitive data, making privacy a critical concern. However, a significant gap remains between the known upper and lower bounds on the regret achievable in linear contextual bandits under Joint Differential Privacy (JDP), which is a popular privacy definition used in this setting. In particular, the best regret upper bound is known to be $O\left(d \sqrt{T} \log(T) + \textcolor{blue}{d^{3/4} \sqrt{T \log(1/\delta)} / \sqrt{\epsilon}} \right)$, while the lower bound is $\Omega \left(\sqrt{d T \log(K)} + \textcolor{blue}{d/(\epsilon + \delta)}\right)$. We discuss the recent progress on this problem, both from the algorithm design and lower bound techniques, and posit the open questions.} }
Endnote
%0 Conference Paper %T Open Problem: What is the Complexity of Joint Differential Privacy in Linear Contextual Bandits? %A Achraf Azize %A Debabrota Basu %B Proceedings of Thirty Seventh Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Shipra Agrawal %E Aaron Roth %F pmlr-v247-azize24a %I PMLR %P 5306--5311 %U https://proceedings.mlr.press/v247/azize24a.html %V 247 %X Contextual bandits serve as a theoretical framework to design recommender systems, which often rely on user-sensitive data, making privacy a critical concern. However, a significant gap remains between the known upper and lower bounds on the regret achievable in linear contextual bandits under Joint Differential Privacy (JDP), which is a popular privacy definition used in this setting. In particular, the best regret upper bound is known to be $O\left(d \sqrt{T} \log(T) + \textcolor{blue}{d^{3/4} \sqrt{T \log(1/\delta)} / \sqrt{\epsilon}} \right)$, while the lower bound is $\Omega \left(\sqrt{d T \log(K)} + \textcolor{blue}{d/(\epsilon + \delta)}\right)$. We discuss the recent progress on this problem, both from the algorithm design and lower bound techniques, and posit the open questions.
APA
Azize, A. & Basu, D.. (2024). Open Problem: What is the Complexity of Joint Differential Privacy in Linear Contextual Bandits?. Proceedings of Thirty Seventh Conference on Learning Theory, in Proceedings of Machine Learning Research 247:5306-5311 Available from https://proceedings.mlr.press/v247/azize24a.html.

Related Material