Differentially Private Submodular Maximization: Data Summarization in Disguise


Marko Mitrovic, Mark Bun, Andreas Krause, and Amin Karbasi. 2017. “Differentially Private Submodular Maximization: Data Summarization in Disguise.” In Proceedings of the 34th International Conference on Machine Learning (ICML 2017).
PDF4.35 MB


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.
Last updated on 01/29/2018