Differentially Private Online Submodular Minimization

Adrian Rivera Cardoso, Rachel Cummings
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:1650-1658, 2019.

Abstract

In this paper we develop the first algorithms for online submodular minimization that preserve differential privacy under full information feedback and bandit feedback. Our first result is in the full information setting, where the algorithm can observe the entire function after making its decision at each time step. We give an algorithm in this setting that is $\eps$-differentially private and achieves expected regret $\tilde{O}\left(\frac{n\sqrt{T}}{\eps}\right)$ over $T$ rounds for a collection of $n$ elements. Our second result is in the bandit setting, where the algorithm can only observe the cost incurred by its chosen set, and does not have access to the entire function. This setting is significantly more challenging due to the limited information. Our algorithm using bandit feedback is $\eps$-differentially private and achieves expected regret $\tilde{O}\left(\frac{n^{3/2}T^{2/3}}{\eps}\right)$.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-cardoso19b, title = {Differentially Private Online Submodular Minimization}, author = {Cardoso, Adrian Rivera and Cummings, Rachel}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {1650--1658}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/cardoso19b/cardoso19b.pdf}, url = {https://proceedings.mlr.press/v89/cardoso19b.html}, abstract = {In this paper we develop the first algorithms for online submodular minimization that preserve differential privacy under full information feedback and bandit feedback. Our first result is in the full information setting, where the algorithm can observe the entire function after making its decision at each time step. We give an algorithm in this setting that is $\eps$-differentially private and achieves expected regret $\tilde{O}\left(\frac{n\sqrt{T}}{\eps}\right)$ over $T$ rounds for a collection of $n$ elements. Our second result is in the bandit setting, where the algorithm can only observe the cost incurred by its chosen set, and does not have access to the entire function. This setting is significantly more challenging due to the limited information. Our algorithm using bandit feedback is $\eps$-differentially private and achieves expected regret $\tilde{O}\left(\frac{n^{3/2}T^{2/3}}{\eps}\right)$.} }
Endnote
%0 Conference Paper %T Differentially Private Online Submodular Minimization %A Adrian Rivera Cardoso %A Rachel Cummings %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-cardoso19b %I PMLR %P 1650--1658 %U https://proceedings.mlr.press/v89/cardoso19b.html %V 89 %X In this paper we develop the first algorithms for online submodular minimization that preserve differential privacy under full information feedback and bandit feedback. Our first result is in the full information setting, where the algorithm can observe the entire function after making its decision at each time step. We give an algorithm in this setting that is $\eps$-differentially private and achieves expected regret $\tilde{O}\left(\frac{n\sqrt{T}}{\eps}\right)$ over $T$ rounds for a collection of $n$ elements. Our second result is in the bandit setting, where the algorithm can only observe the cost incurred by its chosen set, and does not have access to the entire function. This setting is significantly more challenging due to the limited information. Our algorithm using bandit feedback is $\eps$-differentially private and achieves expected regret $\tilde{O}\left(\frac{n^{3/2}T^{2/3}}{\eps}\right)$.
APA
Cardoso, A.R. & Cummings, R.. (2019). Differentially Private Online Submodular Minimization. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:1650-1658 Available from https://proceedings.mlr.press/v89/cardoso19b.html.

Related Material