Differentially Private Submodular Maximization: Data Summarization in Disguise

Marko Mitrovic, Mark Bun, Andreas Krause, Amin Karbasi
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:2478-2487, 2017.

Abstract

Many data summarization applications are captured by the general framework of submodular maximization. As a consequence, a wide range of efficient approximation algorithms have been developed. However, when such applications involve sensitive data about individuals, their privacy concerns are not automatically addressed. To remedy this problem, we propose a general and systematic study of differentially private submodular maximization. We present privacy-preserving algorithms for both monotone and non-monotone submodular maximization under cardinality, matroid, and p-extendible system constraints, with guarantees that are competitive with optimal. Along the way, we analyze a new algorithm for non-monotone submodular maximization, which is the first (even non-privately) to achieve a constant approximation ratio while running in linear time. We additionally provide two concrete experiments to validate the efficacy of these algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-mitrovic17a, title = {Differentially Private Submodular Maximization: Data Summarization in Disguise}, author = {Marko Mitrovic and Mark Bun and Andreas Krause and Amin Karbasi}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {2478--2487}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/mitrovic17a/mitrovic17a.pdf}, url = {https://proceedings.mlr.press/v70/mitrovic17a.html}, abstract = {Many data summarization applications are captured by the general framework of submodular maximization. As a consequence, a wide range of efficient approximation algorithms have been developed. However, when such applications involve sensitive data about individuals, their privacy concerns are not automatically addressed. To remedy this problem, we propose a general and systematic study of differentially private submodular maximization. We present privacy-preserving algorithms for both monotone and non-monotone submodular maximization under cardinality, matroid, and p-extendible system constraints, with guarantees that are competitive with optimal. Along the way, we analyze a new algorithm for non-monotone submodular maximization, which is the first (even non-privately) to achieve a constant approximation ratio while running in linear time. We additionally provide two concrete experiments to validate the efficacy of these algorithms.} }
Endnote
%0 Conference Paper %T Differentially Private Submodular Maximization: Data Summarization in Disguise %A Marko Mitrovic %A Mark Bun %A Andreas Krause %A Amin Karbasi %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-mitrovic17a %I PMLR %P 2478--2487 %U https://proceedings.mlr.press/v70/mitrovic17a.html %V 70 %X Many data summarization applications are captured by the general framework of submodular maximization. As a consequence, a wide range of efficient approximation algorithms have been developed. However, when such applications involve sensitive data about individuals, their privacy concerns are not automatically addressed. To remedy this problem, we propose a general and systematic study of differentially private submodular maximization. We present privacy-preserving algorithms for both monotone and non-monotone submodular maximization under cardinality, matroid, and p-extendible system constraints, with guarantees that are competitive with optimal. Along the way, we analyze a new algorithm for non-monotone submodular maximization, which is the first (even non-privately) to achieve a constant approximation ratio while running in linear time. We additionally provide two concrete experiments to validate the efficacy of these algorithms.
APA
Mitrovic, M., Bun, M., Krause, A. & Karbasi, A.. (2017). Differentially Private Submodular Maximization: Data Summarization in Disguise. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:2478-2487 Available from https://proceedings.mlr.press/v70/mitrovic17a.html.

Related Material