Title: Differentially Private Submodular Maximization: Data Summarization in Disguise

Authors: Marko Mitrovic, Mark Bun, Andreas Krause, Amin Karbasi


Many data summarization applications are cap- tured by the general framework of submodular maximization. As a consequence, a wide range of efficient approximation algorithms have been developed. However, when such applications in- volve sensitive data about individuals, their pri- vacy concerns are not automatically addressed. To remedy this problem, we propose a gen- eral 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 solutions. Along the way, we ana- lyze a new algorithm for non-monotone submod- ular maximization under a cardinality constraint, which is the first (even non-privately) to achieve a constant approximation ratio with a linear num- ber of function evaluations. We additionally pro- vide two concrete experiments to validate the ef- ficacy of these algorithms.

Full Text: [PDF]

Accessibility at Yale   Inference, Information, and Decision Group at Yale