Streaming Submodular Maximization with Differential Privacy

Anamay Chaturvedi, Huy Nguyen, Thy Dinh Nguyen
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:4116-4143, 2023.

Abstract

In this work, we study the problem of privately maximizing a submodular function in the streaming setting. Extensive work has been done on privately maximizing submodular functions in the general case when the function depends upon the private data of individuals. However, when the size of the data stream drawn from the domain of the objective function is large or arrives very fast, one must privately optimize the objective within the constraints of the streaming setting. We establish fundamental differentially private baselines for this problem and then derive better trade-offs between privacy and utility for the special case of decomposable submodular functions. A submodular function is decomposable when it can be written as a sum of submodular functions; this structure arises naturally when each summand function models the utility of an individual and the goal is to study the total utility of the whole population as in the well-known Combinatorial Public Projects Problem. Finally, we complement our theoretical analysis with experimental corroboration.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-chaturvedi23a, title = {Streaming Submodular Maximization with Differential Privacy}, author = {Chaturvedi, Anamay and Nguyen, Huy and Nguyen, Thy Dinh}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {4116--4143}, 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/chaturvedi23a/chaturvedi23a.pdf}, url = {https://proceedings.mlr.press/v202/chaturvedi23a.html}, abstract = {In this work, we study the problem of privately maximizing a submodular function in the streaming setting. Extensive work has been done on privately maximizing submodular functions in the general case when the function depends upon the private data of individuals. However, when the size of the data stream drawn from the domain of the objective function is large or arrives very fast, one must privately optimize the objective within the constraints of the streaming setting. We establish fundamental differentially private baselines for this problem and then derive better trade-offs between privacy and utility for the special case of decomposable submodular functions. A submodular function is decomposable when it can be written as a sum of submodular functions; this structure arises naturally when each summand function models the utility of an individual and the goal is to study the total utility of the whole population as in the well-known Combinatorial Public Projects Problem. Finally, we complement our theoretical analysis with experimental corroboration.} }
Endnote
%0 Conference Paper %T Streaming Submodular Maximization with Differential Privacy %A Anamay Chaturvedi %A Huy Nguyen %A Thy Dinh Nguyen %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-chaturvedi23a %I PMLR %P 4116--4143 %U https://proceedings.mlr.press/v202/chaturvedi23a.html %V 202 %X In this work, we study the problem of privately maximizing a submodular function in the streaming setting. Extensive work has been done on privately maximizing submodular functions in the general case when the function depends upon the private data of individuals. However, when the size of the data stream drawn from the domain of the objective function is large or arrives very fast, one must privately optimize the objective within the constraints of the streaming setting. We establish fundamental differentially private baselines for this problem and then derive better trade-offs between privacy and utility for the special case of decomposable submodular functions. A submodular function is decomposable when it can be written as a sum of submodular functions; this structure arises naturally when each summand function models the utility of an individual and the goal is to study the total utility of the whole population as in the well-known Combinatorial Public Projects Problem. Finally, we complement our theoretical analysis with experimental corroboration.
APA
Chaturvedi, A., Nguyen, H. & Nguyen, T.D.. (2023). Streaming Submodular Maximization with Differential Privacy. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:4116-4143 Available from https://proceedings.mlr.press/v202/chaturvedi23a.html.

Related Material